Cho lưới ô vuông A kích thước
m´n, các hàng được đánh
số từ 1 đến m từ trên xuống dưới, các cột được đánh số từ trái sang phải, từ 1
đến n. Mỗi ô của lưới chứa một số nguyên có giá trị tuyệt đối không vượt quá 109.
Từ một ô có thể đi sang ô kề
cạnh bên phải hoặc xuống dưới. Xét các đường đi theo quy tắc trên từ ô trên
trái xuống ô dưới phải. Tổng các số trên những ô đã đi qua là giá trị của đường
đi.
Hãy xác định giá trị lớn nhất
có thể đạt được.
Dữ liệu: Vào
từ file route.inp, dòng đầu tiên chứa 2 số nguyên m và n (2 £ m, n £
1000), mỗi dòng trong m dòng sau chứa n số nguyên xác định một dòng của bảng.
Kết quả: Đưa
ra file route.out một số nguyên – giá trị max tìm được.
Ví
dụ:
ROUTE.INP
|
ROUTE.OUT
|
5 6
2 6 8
1 – 5 9
9 1 7
3 6 4
-2 0
5 1 8 -6
1 4 0
3 0 4
9 -2
4 5 -4 2
|
46
|
