Minimum Cost Path in Grid

Given an R × C 2D grid filled with non-negative integers, find a path from the top-left cell (0, 0) to the bottom-right cell (R - 1, C - 1) that minimizes ​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​‌‌​​​‌​​​‌‌​​​‌​​‌‌​​​​​‌‌​​​‌‌​​‌‌​‌​​​​‌‌​‌​‌​​‌‌​‌​​​​‌‌​‌‌​​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​‌​​​​‌‌​‌​​​​‌‌​​​​​​‌‌​​​‌the total sum of all numbers along its path.

At each step, you can only move right or down.

---

Input Format

• Line 1: Two space-separated integers R and C (1 ≤ R, C ≤ 500), representing the number of rows and columns.
• Next R lines: Each line contains C space-separated non-negative integers representing the grid cell values (0 ≤ Grid[i][j] ≤ 1000). ​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​‌‌​​​‌​​​‌‌​​​‌​​‌‌​​​​​‌‌​​​‌‌​​‌‌​‌​​​​‌‌​‌​‌​​‌‌​‌​​​​‌‌​‌‌​​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​‌​​​​‌‌​‌​​​​‌‌​​​​​​‌‌​​​‌

---

Output Format

• Print a single integer representing the minimum path sum from (0, 0) to (R - 1, C - 1).

---

Example 1

Input:

3 3
1 3 1
1 5 1
4 2 1

Output:

7

Explanation: The optimal path is (0, 0) → (0, 1) → (0, 2) → (1, 2) → (2, 2) with cell values 1 + 3 + 1 + 1 + 1 = 7.

---

Example 2

​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​‌‌​​​‌​​​‌‌​​​‌​​‌‌​​​​​‌‌​​​‌‌​​‌‌​‌​​​​‌‌​‌​‌​​‌‌​‌​​​​‌‌​‌‌​​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​‌​​​​‌‌​‌​​​​‌‌​​​​​​‌‌​​​‌ Input:

2 3
1 2 3
4 5 6

Output:

12

Explanation: The path (0, 0) → (0, 1) → (0, 2) → (1, 2) gives 1 + 2 + 3 + 6 = 12. ​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​‌‌​​​‌​​​‌‌​​​‌​​‌‌​​​​​‌‌​​​‌‌​​‌‌​‌​​​​‌‌​‌​‌​​‌‌​‌​​​​‌‌​‌‌​​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​‌​​​​‌‌​‌​​​​‌‌​​​​​​‌‌​​​‌

2 3
1 2 3
4 5 6

12

3 3
1 3 1
1 5 1
4 2 1

7