Mô Tả Bài Toán:

Trên một lưới vuông MxN (0 ≤ M, N ≤ 100), người ta để mỗi ô một lượng thức ăn A[i][j]. Một chú gián xuất phát từ ô (1,1) đi đến ô (M, N). Chú gián chỉ có thể đi qua một ô kề cạnh bên phải hoặc một ô bên dưới ô đang đứng, mỗi lần đi qua một ô chú gián ăn một lượng thức ăn trong ô đó. Hãy chi ra đường đi mà chú gián khi đi qua có thể ăn một lượng thức ăn lớn nhất.

Dữ Liệu Vào:

• Dòng đầu tiên chứa hai số nguyên M, N.
• Dòng thứ hai chứa các giá trị A[i][j] tương ứng với ma trận MxN.

Dữ Liệu Ra:

• Xuất kết quả: Lượng thức ăn lớn nhất mà chú gián có thể ăn.

Ví Dụ:

Dữ Liệu Vào:

4 4
9 5 10 9
9 16 8 6
2 6 7 3
7 6 9 2

Kết Quả:

52

Giải Thích:

• Để đạt được lượng thức ăn tối đa, chú gián có thể đi qua các ô theo đường chéo từ trái sang phải và từ trên xuống dưới. Tổng thức ăn ăn được là 9 + 16 + 7 + 6 + 10 + 5 = 52.