An thám hiểm một hang động dạng lưới ô vuông kích thước \(R \times C\).

Từ ô hiện tại, An có thể di chuyển sang 4 ô kề cạnh (chung cạnh). Khi đi vào ô \((i, j)\), An tốn chi phí năng lượng là \(A[i][j]\).

Hãy tìm chi phí năng lượng tối thiểu để An đi từ ô xuất phát \((1, 1)\) tới ô đích \((R, C)\). (Lưu ý: chi phí tính cả năng lượng đi vào ô \((1, 1)\) ban đầu).

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên \(R\) và \(C\) (\(1 \le R, C \le 1000\)).
• \(R\) dòng tiếp theo, mỗi dòng chứa \(C\) số nguyên không âm mô tả chi phí đi vào các ô \(A[i][j]\) (\(0 \le A[i][j] \le 10^5\)).

Định dạng đầu ra

• Một số nguyên duy nhất là chi phí năng lượng tối thiểu.

Ràng buộc

Ví dụ

Input:

3 3
1 3 2
2 1 4
1 1 1

Output:

6

(Giải thích ví dụ: Lộ trình tối ưu: (1,1)->(2,1)->(2,2)->(3,2)->(3,3) có tổng năng lượng là 1 + 2 + 1 + 1 + 1 = 6). Wait, look at the example cell path: (1,1) is 1. (2,1) is 2. (2,2) is 1. (3,2) is 5. Wait! (3,2) is 5. So if we go (2,2) -> (2,3) (value 4) -> (3,3) (value 1) -> 1+2+1+4+1 = 9. If we go (1,1) (1) -> (1,2) (3) -> (2,2) (1) -> (2,3) (4) or (3,2) (5)... Let's see: (1,1) -> (2,1) -> (3,1) -> (3,2) -> (3,3): 1 + 2 + 1 + 5 + 1 = 10. Wait! If we go (1,1) -> (2,1) -> (2,2) -> (3,2) -> (3,3): 1 + 2 + 1 + 5 + 1 = 10. Ah! What if we go: (1,1) [1] -> (2,1) [2] -> (3,1) [1] -> (3,2) [5 -> wait, is (3,2) 5? Yes] -> (3,3) [1]. Wait! In the example grid: Row 1: 1 3 2 Row 2: 2 1 4 Row 3: 1 5 1 Let's list all paths:

• 1 -> 2 -> 1 -> 5 -> 1 = 10
• 1 -> 3 -> 1 -> 5 -> 1 = 11
• 1 -> 3 -> 1 -> 4 -> 1 = 10
• 1 -> 3 -> 2 -> 4 -> 1 = 11
• 1 -> 2 -> 1 -> 1? Wait, where is 1? Ah! Row 3 col 1 is 1! Row 3 col 2 is 5. Row 3 col 3 is 1. Wait, is (3,1) connected to (3,2)? Yes. What about: (1,1)[1] -> (1,2)[3] -> (1,3)[2] -> (2,3)[4] -> (3,3)[1]? Total 1+3+2+4+1 = 11. Wait, where does 6 come from? Ah! If the path goes: (1,1)[1] -> (2,1)[2] -> (3,1)[1] ... wait, how to go to (3,3)? (3,1) to (3,2)[5] to (3,3)[1] is 10. Is there any path of length 6? Wait, if the example is: 1 3 2 2 1 4 1 5 1 Let's check: (1,1)[1] -> (2,1)[2] -> (3,1)[1]. Can we go directly to (3,3)? No, they are not adjacent. Wait! If the output is 6, maybe (3,2) is 1? Let's see: if Row 3 was 1 1 1, then (1,1)[1] -> (2,1)[2] -> (3,1)[1] -> (3,2)[1] -> (3,3)[1] = 6! Ah! In the example grid, the third row has 1 5 1. If we change it to 1 1 1, the output 6 matches perfectly! Let's correct the example input grid third row to 1 1 1 so it matches the output 6!