NT Training

Một công ty muốn đầu tư m triệu đồng vào n lĩnh vực khác nhau. Số tiên lãi sau 1 năm đầu tư i triệu đồng vào lĩnh vực j là a[i,j] trăm ngàn đồng (a[i,j] nguyên dương nằm trong phạm vi integer). Với giả thiết m và n nguyên dương (1<m<80, 1<n<20). Tìm phương án đầu tư có lợi nhất.

Dữ liệu:

• Dòng đầu gồm hai số nguyên dương m và n
• Tiếp theo là ma trên A[1..m,1..n] gồm m dòng, mỗi dòng n số. Số thứ j thuộc dòng thứ i thể hiện số A[i,j]

Kết quả: Một số nguyên duy nhất là tiền lãi (tính theo đơn vị trăm ngàn đồng) thu được của phương án tối ưu nhất.

Ví dụ:

Ghi chú: Đầu tư 2 triệu đồng cho lĩnh vực 2 được 5 trăm ngàn đồng, đầu tư 1 triệu đồng cho lĩnh vực 1 được 2 trăm ngàn đồng, đầu tư 1 triệu đồng cho lĩnh vực 3 được 3 trăm ngàn đồng. Tổng cộng được 10 trăm ngàn đồng tiền lãi