Minimum Path Sum in a Grid

Ellerby Port charges to move a container across its yard. The yard is a rectangle of bays and every bay has a posted fee. A crane starts at the top-left bay and must finish at the bottom-right one, shifting the container one bay right or one bay down at a time, never back the way it came. Every bay it rests in is charged, first and last included.

Task: Print the cheapest total fee for getting the container across the yard.

Input

The first line holds two integers separated by a space: the number of bay rows, then the number of bay columns, each between 1 and 200. Each of the next lines holds one row of the yard: that many integers separated by single spaces, read top row first. Every fee is 0 or more.

Output

One line holding a single integer: the smallest total of the fees along one route from the top-left bay to the bottom-right bay. Only rightward and downward moves are allowed. Both the first and the last bay are charged.

Example:

Input:
3 3
1 3 1
1 5 1
4 2 1

Output:
7

(path 1→3→1→1→1 sums to 7)