Trong một cuộc thi điều khiển robot của trường ICTU, mỗi đội điều khiển một robot di chuyển trong một khu vực được chia thành lưới có M hàng và N cột. Mỗi ô trong lưới chứa một lượng năng lượng nhất định mà robot có thể thu thập. Robot bắt đầu tại ô ở góc trên bên trái (ô (1, 1)) và cần di chuyển đến ô ở góc dưới bên phải (ô (M, N)). Robot chỉ có thể di chuyển sang phải hoặc xuống dưới mỗi lần. Lưu ý: Robot không thể quay ngược lại hoặc di chuyển sang trái hay lên trên. Mục tiêu của đội là giúp robot thu thập được nhiều năng lượng nhất trên đường đi.

Tuy nhiên, việc di chuyển của robot gặp phải nhiều thách thức. Một số ô trong lưới có thể bị chặn (mức năng lượng là số âm), và robot không thể đi qua các ô này. Đội cần tìm cách tối ưu để robot thu thập năng lượng mà không bị kẹt.

Input:

• Dòng đầu tiên chứa hai số nguyên M và N (1 ≤ M, N ≤ 1000) - là kích thước của lưới.
• M dòng tiếp theo, mỗi dòng chứa N số nguyên. Mỗi số nguyên đại diện cho năng lượng tại ô tương ứng, trong đó:
  • Năng lượng tại mỗi ô là một số nguyên không âm (0 ≤ năng lượng ≤ 1000).
  • Nếu ô bị chặn, năng lượng tại ô đó là -1.

Output:

• In ra tổng năng lượng lớn nhất mà robot có thể thu thập được khi đi từ ô (1, 1) đến ô (M, N). Nếu robot không thể đến đích, in ra -1.

Ví dụ:

Input 1:

3 3
1 2 3
4 -1 6
7 8 9

Output 1:

29

Giải thích: Đường đi tối ưu là: 1 → 4 → 7 → 8 → 9, với tổng năng lượng là 29. Robot tránh được ô bị chặn.

Input:

3 3
1 -1 3
4 -1 6
-1 8 9

Output:

-1

Giải thích: Robot không thể đi từ ô (1, 1) đến ô (M, N) do các ô bị chặn trên đường đi.