Minimum Cost Path

You have been given a matrix of ‘N’ rows and ‘M’ columns filled up with integers. Find the minimum sum that can be obtained from a path which from cell (x,y) and ends at the top left corner (1,1).

From any cell in a row, we can move to the right, down or the down right diagonal cell. So from a particular cell (row, col), we can move to the following three cells:

Down: (row+1,col)
Right: (row, col+1)
Down right diagonal: (row+1, col+1)

Input Format:

The first line will contain two integers ‘N’ and ‘M’ denoting the number of rows and columns, respectively.

Next ‘N’ lines contain ‘M’ space-separated integers each denoting the elements in the matrix.

The last line will contain two integers ‘x’ and ‘y’ denoting the cell to start from.

Output Format:

For each test case, print an integer that represents the minimum sum that can be obtained by traveling a path as described above.

Output for every test case will be printed in a separate line.

Note:

You don’t need to print anything; It has already been taken care of.

Constraints:

1 <= T <= 50
1 <= N, M <= 100
-10000 <= cost[i][j] <= 10000
1 <= x, y <= 100

Time limit: 1 sec

Sample Input 1:

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

Sample Output 1:

12

Explanation For sample input 1:

The minimum cost path will be (0, 0) -> (1, 1) -> (2, 3), So the path sum will be (3 + 1 + 8) = 12, which is the minimum of all possible paths.

Sample Input 2:

3 4
11 2 8 6 
2 12 17 6 
3 3 1 8 
3 4

Sample Output 2:

25