Minimum Cost Path

You are given a grid of size \(n \times m\). Each cell in the grid contains a non-negative cost. Your task is to find the minimum cost path from the top-left corner \((1,1)\) to the bottom-right corner \((n,m)\). You can only move either right or down at any point in time.

The recurrence relation for the dynamic programming solution is given by:

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

Note: For the cells in the first row or the first column, the path can only come from the left or above respectively.

inputFormat

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

• The first line contains two integers \(n\) and \(m\), representing the number of rows and columns respectively.
• Then follow \(n\) lines each containing \(m\) space-separated integers representing the grid.

outputFormat

For each test case, output a single line containing the minimum cost required to travel from the top-left corner to the bottom-right corner.

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

7