Đề bài

Cho ma trận N × M gồm các số nguyên (có thể âm hoặc dương).

• Bắt đầu từ ô (1,1), chỉ được đi xuống (↓) hoặc phải (→).

• Tìm tổng đường đi lớn nhất từ (1,1)→(N,M).

Dữ liệu vào

Dòng 1: \(N M (1 ≤ N, M ≤ 1000)\)

N dòng tiếp theo: mỗi dòng M số nguyên \((-10^6 ≤ a[i][j] ≤ 10^6)\)

Dữ liệu ra

Một số nguyên – tổng lớn nhất có thể đạt được.

Ví dụ