Minimum Path Sum

You are given a grid of integers with m rows and n columns. Your task is to find the minimum path sum from the top-left cell to the bottom-right cell. You can only move either to the right or down at any step.

Let \( grid[i][j] \) denote the value at cell \( (i, j) \) (0-indexed). Define a DP table \( dp \) where

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

with the initial conditions ( dp[0][0] = grid[0][0] ), the first row computed as ( dp[0][j] = dp[0][j-1] + grid[0][j] ), and the first column computed as ( dp[i][0] = dp[i-1][0] + grid[i][0] ). The answer is given by ( dp[m-1][n-1] ).

Input will be provided via standard input and the result should be output to standard output.

inputFormat

The first line contains an integer T, the number of test cases. For each test case:

• The first line contains two integers m and n, representing the dimensions of the grid.
• This is followed by m lines, each containing n space-separated integers representing the grid.

All input is read from standard input.

outputFormat

For each test case, output a single line containing the minimum path sum from the top-left to the bottom-right of the grid. All output should be written to standard output.

## sample

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

7

</p>