You are given an ~N \times M~ grid of squares. Each square contains a number ~a_i~, ~1 \le i \le N \times M~, the cost to travel through that square. You are starting at the most top-left square. At each turn you may choose to move down or right but not both. Find the minimum cost it would take you to travel to the most bottom-right square.

Constraints

In all tests,
~2 \le N, M \le 500~
~1 \le a_i \le 10^6~

Input Specification

The first line contains two integers, ~N~ and ~M~, the dimensions of the grid of squares (~N~ rows and ~M~ columns).
The next ~N~ lines each contains ~M~ integers, ~a_i~, the cost to travel through that square in the grid.

Output Specification

Output on a single line, the minimum sum of costs to travel from the most top-left square to the most bottom-right square.

Sample Input

3 4
3 1 2 4
9 8 7 6
2 8 9 2

Sample Output

18

Explanation for Sample Output

We can take the path ~3 \to 1 \to 2 \to 4\to 6 \to 2~, which gives us the sum of ~18~. There are no paths that yield a smaller sum.