Mô Tả Bài Toán:

Cho bảng a gồm m x n ô vuông đơn vị. Mỗi ô ghi một số nguyên là giá trị mệnh giá tiền (đơn vị nghìn đồng) và có giá trị không vượt quá |100. Robot đặt tại cột 1 sẽ di chuyển đến cột n với quy tắc: từ ô (i, j), robot chỉ có thể di chuyển đến một trong 3 ô kề bên phải ô đang đứng.

Yêu cầu: Tìm con đường đi cho robot sao cho thu được nhiều tiền nhất.

Dữ Liệu Vào:

• Dòng 1: Ghi 2 số nguyên m, n (0 < m, n ≤ 200)
• M dòng sau, mỗi dòng ghi n số thể hiện mức giá trị tiền .

Dữ Liệu Ra:

- 1 Dòng: Ghi tổng mức thu nhặt nhiều tiền nhất.

Ví Dụ:

Dữ Liệu Vào:

6 6
1 10 200 50 20 20
2 5 2 100 5 100
5 2 2 10 1 5
10 5 1 50 2 200

Kết Quả:

575

Giải Thích: