Minimum Path Sum in a Grid

You are given a rectangular grid of non-negative integers. Your task is to find a path from the top-left corner to the bottom-right corner of the grid such that the sum of the numbers along the path is minimized. You can only move either down or right at any point in time.

Input Constraints:

• Let \(M\) be the number of rows and \(N\) be the number of columns in the grid.
• The grid cells contain non-negative integers.

Hint: Use dynamic programming where each cell \(dp[i][j]\) represents the minimum path sum to reach cell \((i, j)\). The recurrence is given by:

[ dp[i][j] = \min(dp[i-1][j],,dp[i][j-1]) + grid[i][j] ]

inputFormat

The first line of input contains an integer T representing the number of test cases.

For each test case:

• The first line contains two space-separated integers M and N, representing the number of rows and columns in the grid.
• This is followed by M lines, each containing N space-separated integers representing the grid.

outputFormat

For each test case, output the minimal path sum from the top-left corner to the bottom-right corner on a new line.

## sample

1
3 3
1 3 1
1 5 1
4 2 1

7

</p>