Minimum Path Cost in Grid

You are given a 2D grid of integers where each cell represents a cost. Your task is to find the minimum cost path from the top-left corner to the bottom-right corner of the grid. You are only allowed to move either right or down at each step.

The cost of a path is the sum of the values in the cells along the path. The problem may include multiple test cases.

The problem can be formulated mathematically as follows: Let \(dp(i,j)\) denote the minimum cost to reach cell \((i,j)\) from \((0,0)\). Then:

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

Boundary Conditions:

• \(dp(0,0)=grid(0,0)\)
• \(dp(i,0)=dp(i-1,0)+grid(i,0)\) for \(i>0\)
• \(dp(0,j)=dp(0,j-1)+grid(0,j)\) for \(j>0\)

inputFormat

The input begins with an integer (T) denoting the number of test cases. Each test case starts with two integers (R) and (C) representing the number of rows and columns, respectively, followed by (R) lines each containing (C) space-separated integers (the grid values).

outputFormat

For each test case, output a single integer — the minimum cost to reach the bottom-right corner from the top-left corner. Each result should be printed on its own line.## sample

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

7
3