Cho một bảng kích thước ( dòng, cột), trên đó ghi các số nguyên . Một người xuất phát tại ô nào đó của cột , cần sang cột (tại ô nào cũng được).
Quy tắc đi: Từ ô chỉ được quyền sang một trong ô .
Hãy tìm một đường đi sao cho tổng tất cả các số trên đường đi đó là lớn nhất.
Dữ liệu vào:
- Dòng đầu ghi hai số là số hàng và số cột của bảng;
- dòng tiếp theo, dòng thứ ghi số trên hàng của bảng theo đúng thứ tự từ trái qua phải.
Dữ liệu ra:
- Gồm một dòng duy nhất ghi tổng lớn nhất tìm được.
Ví dụ:
Dữ liệu vào:
5 7
9 -2 6 2 1 3 4
0 -1 6 7 1 3 3
8 -2 8 2 5 3 2
1 -1 6 2 1 6 1
7 -2 6 2 1 3 7
Dữ liệu ra:
Giải thích:
- Đường đi được mô tả là các ô xanh trong hình dưới đây:
Giới hạn:
