Skip to content
UPEEC

Minimum Path Sum

Medium#dynamic-programming#matrix· solved by 0 · time limit 2.0 s

Walk from the top-left to the bottom-right cell of a grid, moving only right or down. Minimise the sum of the cells you visit.

Input

RR and CC, then RR rows of CC non-negative integers.

Output

The minimum sum.

Constraints

1≤R,C≤5001 \le R, C \le 500

Sample 1

Input

3 3
1 3 1
1 5 1
4 2 1

Output

7

Sign in or join free to run and submit your solution.