Minimum path sum

Given a grid of height h and width w filled with integers, you are asked to find a path from the top-left to the bottom-right corner that minimizes the sum of numbers along the path. You are only allowed to move right or down.
 
3
2
1
3
1
9
2
3
9
1
5
4

Input

The first line of the input contains two integers h and w (1 ≤ h, w ≤ 1000).
The next h lines contain w space-separated integers representing the values in the grid .

Output

The program should print the minimum possible sum to get from the top-left corner to the bottom-right corner.

Examples

Input
Output
3 4 3 2 1 3 1 9 2 3 9 1 5 4
15

Explanation

We can move: 3 → 2 → 1 → 2 → 3 → 4
 
Hint 1
The state in a dynamic programming problem can be a 2-dimensional array.
Hint 2
It can represent the best possible solution up to that coordinate (d[r][c] represents the best path to reach the row r and the column c).
 

Why doesn’t the greedy approach work here? Imagine if you always moved in the direction of the smallest possible value. What would be the issue there?
 

Constraints

Time limit: 3 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue