Ahmed,Jairam and Shreyas secured the 2nd Place Round 1 in NPL. They have friends who are girls. Since all the girls asked the three to treat them in canopy. But there were so many.So the three, themselves created a puzzle. The puzzle is that the M*N Girls should stand in matrix format each one will be having a board stating the money needed for their appetite.They have to start from top-left girl and end in the bottom-right girl in such a way that the travel should incurred them the least money. You can only traverse down, right and diagonally lower cells from a given cell, i.e., from a given cell (i, j), cells (i+1, j), (i, j+1) and (i+1, j+1) can be traversed. If they are able to do such a travel, then all the girls need to treat them otherwise they have to treat them all.
Input:
M N (1 <= M,N <= 10 )
Then a M*N Matrix Follows.
Output:
Print the Least Money.
First Test Case 1 2 3 4 8 2 1 5 3 They start at 1.(0,0) They should traverse this way to get the minimal cost of 8. 1->2->2->3