Boys Vs Girls

0

0 votes
Problem

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.

Sample Input
2
3 3
1 2 3
4 8 2
1 5 3
6 3
34 36 24
21 32 47
15 50 40
10 8 14
45 9 3
49 18 22
Sample Output
8
103
Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

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

Editor Image

?