Gửi bài giải

Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Pascal, PyPy, Python

Cho bảng số gồm ~M~ hàng và ~N~ cột, hàng thứ ~i~ cột thứ ~j~ của bảng số gọi là ô (~i,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 cả ô (~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 ~a_i1,a_i2,…,a_iN~ (~|a_ij│≤100~);

Output

In ra giá trị của đường đi tìm được.

Ví dụ:

input

3 3
1 2 3
2 3 -4
-5 3 7

output

16


Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.