Thu hoạch năng lượng lớn nhất

Bối cảnh và bài toán

Mỗi ô có thể cộng hoặc trừ năng lượng. Robot chỉ đi xuống/phải và phải đi từ góc trên trái tới góc dưới phải.

Yêu cầu

Tìm tổng năng lượng lớn nhất có thể thu được.

Input

Dòng 1: n m; sau đó ma trận số nguyên.

Output

In tổng lớn nhất.

Ràng buộc

• 1 <= n,m <= 1000
• -1000 <= a[i][j] <= 1000

Chấm điểm

Ví dụ 1

Input

2 3
1 -2 3
4 5 -1

Output

9

Giải thích. Ví dụ nhỏ giúp kiểm tra cách mô hình hóa trạng thái và kết quả cuối; khi tự giải, cần suy luận từ ràng buộc thay vì suy đoán từ sample.

Ví dụ 2

Input

1 1
-7

Output

-7

Giải thích. Hãy đối chiếu với edge case: trạng thái đầu, trạng thái không đạt được, tie hoặc biên chỉ số tùy bài.

Thông tin bài tập

Nguồn: FULLHOUSE DEV – Self-generated.