Max 2 -Bờm chọn quà

Tên file bài làm: MAX2.*

Sau một thời gian ngắn Phú ông nhanh chóng thăng quan tiến chức lên làm Lý trưởng rồi Chi phủ và bây giờ đã là quan Thượng Thư và được giao nhiệm vụ tổ chức cuộc thi chọn nhân tài cho đất nước.

Người thắng cuộc lần này lại là Bờm khiến cho quan Thượng Thư rất tức giận. Trước khi trao quà cho Bờm thì ông ta lại đánh tráo 1 số phần quà nào đó thành đá tảng nếu Bờm chọn lấy hết quà thì phải tốn tiền thuê xe mang về trong khi mấy tảng đá lại không có ý nghĩa gì cả mà nếu để lại thì bị khép vào tội coi thường triều đình.

Lần này quan Thượng Thư bố trí các phần quà trên một hình chữ nhật mà mỗi ô vuông đơn vị của hình chữ nhật chứa một phần quà. Bờm có thể chọn hết tất cả các phần quà mang về hoặc có thể chọn một số phần quà nào đó sao cho các phần quà Bờm chọn tạo thành một hình chữ nhật bên trong hình chữ nhật ban đầu.

Cũng nhờ bảo bối của Đô-rê-mon mà Bờm biết được giá trị các phần quà có thể nhận là một số nguyên. Trước khi  nhận quà Bờm mô tả các phần quà thành một bảng có n dòng m cột, ô ở dòng i cột j chứa số nguyên a_ij có thể là quà có giá trị hoặc đá, nếu đó là đá thì a_ij≤0 và phải mất |a_ij| tiền để chở về nhà.

Hãy giúp Bờm chọn quà sao cho tổng giá trị mang về nhà là lớn nhất.

Dữ liệu vào: từ tệp MAX2.INP

+ Dòng đầu tiên ghi hai số nguyên dương n và m (n, m ≤ 400)

+ Dòng thứ i  trong n dòng tiếp theo chứa các số a_i1, a_i2, a_i3,…,a_im  (|a_ij| ≤10⁴)

Dữ liệu ra: ghi vào tệp MAX2.OUT một số nguyên duy nhất là giá trị của bài toán

Ví dụ:

MAX2.INP	MAX2.OUT
4 5  2  3  1 -10  1  2  0 -1  -5 -2 -1  0  2   1 -1  2 -1 -2  -4  3	8

 Giải thích: Các phần quà Bờm chọn được in đậm.

 Test - Code - Solution

back <----> next