In a rectangular table NxM (in each cell of which a certain number is written), at the beginning the player is in the upper left cell.
In one move, he is allowed to move to the next cell either to the right or down (it is forbidden to move to the left and up).
When passing through a cell, the player is charged as much c.u.
It is required to find the minimum amount of c.u., by paying which the player can get to the lower right corner.
Input:
- the first line contains two numbers N and M - table sizes (\(1<=N<=20 \), \(1<=M<=20\));
- then there are N lines of M numbers in each - sizes of fines in c.u. for passing through the corresponding cells (each number from 0 to 100).
Output: print the minimum amount you can spend to get in the lower right corner.
Examples
| # |
Input |
Output |
| 1 |
3 4
1 1 1 1
5 2 2 100
9 4 2 1
|
8 |