----- Nội dung ảnh -----
DP_A10
Cho bảng số gồm M hàng và N cột, hàng thứ i cột thứ j có giá trị a(i,j). Một con ROBOT nếu đặt trên bảng số tại ô (i,j) thì nó chỉ có thể đi đến ô (i+1,j) hoặc (i,j+1).
Yêu cầu:
Giả sử đặt con ROBOT ban đầu tại ô (1,1). Hãy tìm đường đi từ ô (1,1) đến ô (M,N) sao cho giá trị đường đi của ROBOT là lớn nhất. Giá trị của một đường đi là tổng các giá trị của các ô nằm trên đường đi đó (bao gồm ô (1,1) và ô (M,N)).
Input
-Dòng đầu gồm hai số nguyên dương M và N (M, N ≤ 3000);
-M dòng tiếp theo mỗi dòng gồm N số nguyên a1, a2, ..., aN (|ai| ≤ 100);
Output
In ra giá trị của đường đi tìm được.
