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.

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!

Ràng buộc