Attempt

Please login to see your submissions result.

Problem

Tại hầm mộ của vương triều cổ, bạn đứng trước một mê cung lát đá hình lưới có ~N~ hàng và ~M~ cột. Mỗi ô khắc một con số thể hiện năng lượng bạn thu được khi đặt chân lên đó.
Bạn khởi hành từ ô ~[1,1]~ và mục tiêu là ô ~[N,M]~. Lời nguyền của hầm mộ chỉ cho phép bạn đi sang phải hoặc đi xuống mỗi bước.
Hãy tìm Lối Vàng – con đường giúp tổng năng lượng thu được lớn nhất từ ~[1,1]~ đến ~[N,M]~.

Input

• Dòng đầu: hai số nguyên ~N, M~.
• ~N~ dòng tiếp theo, mỗi dòng gồm ~M~ số nguyên ~A[i][j]~ — năng lượng tại ô hàng ~i~, cột ~j~.

Output

In ra tổng năng lượng lớn nhất có thể đạt được khi đi từ ~[1,1]~ đến ~[N,M]~ theo các quy tắc di chuyển.

Constraints

• ~1 \le N, M \le 100~
• ~1 \le A[i][j] \le 10^9~

Sample