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?