THỰC HÀNH

Thành phố Sơn La đang trên đà phát triển. Để thay đổi bộ mặt của Thành phố, công ty Đô thị quyết định trồng lại cây trên các tuyến đường trong Thành Phố, trong đó có tuyến đường Trường Chinh là một tuyến đường vô cùng quan trọng, một trục dọc của Thành Phố. Dọc theo tuyến đường này, công ty đã dự kiến quy hoạch được N vị trí trồng cây đánh số từ 1 đến N và đã chọn được M loại cây đánh số từ 1 đến M. Theo phong thủy thì M loại cây này phải được trồng theo đúng thứ tự trên, có nghĩa là nếu hai cây i₁ và i₂ được trồng vào hai vị trí j₁ và j₂ mà i₁ < i₂ thì j₁ < j₂. Theo đánh giá thì nếu cây thứ i được trồng vào vị trí j thì có “độ đẹp” là C_ij.

Yêu cầu: Cho biết N, M và các độ đẹp C_ij (i = 1...M, j = 1...N). Bạn hãy giúp công ty Đô thị tìm phương án trồng cây sao cho hợp phong thủy và có tổng “độ đẹp” lớn nhất.

Dữ liệu vào:

• Dòng đầu chứa hai số nguyên dương N và M.
• M dòng tiếp theo, dòng thứ i chứa N số nguyên C_i1, C_i2, …, C_iN.

Hai số liên tiếp trên một dòng được ghi cách nhau một dấu cách.

Dữ liệu ra:

Ghi ra một số nguyên duy nhất là tổng “độ đẹp” lớn nhất có thể được.

Ví dụ:

Dữ liệu vào:
3 2
100 50 -80
-50 -20 100

Dữ liệu ra:
200

Giải thích: Ta có 3 cách trồng như sau với tổng “độ đẹp” tương ứng:

Như vậy cách trồng để có tổng độ đẹp lớn nhất là cây số 1 trồng vào vị trí số 1 và cây số 2 trồng vào vị trí số 3.

Giới hạn: Trong tất cả các bộ dữ liệu (test) có: 1 ≤ M ≤ N ≤ 100; |C_ij| ≤ 1000 (i = 1...M, j = 1...N)

• Subtask #1: 60% số test ứng với 60% số điểm của bài có 1 ≤ M ≤ N ≤ 30.
• Subtask #2: 10% số test khác ứng với 10% số điểm của bài có N – M = 1.
• Subtask #3: 30% số test còn lại ứng với 30% số điểm của bài không có ràng buộc gì thêm.