Minimum Energy Path Grid Problem

You are given a 2D grid of non-negative integers. Each cell in the grid represents the energy cost of stepping on that cell. A robot starts at the top-left corner ((0, 0)) and must reach the bottom-right corner ((N-1, M-1)). The robot can only move right or down. The task is to compute the minimum energy cost required to reach the destination.

The dynamic programming recurrence is given by: [ dp[i][j] = \min\left(dp[i-1][j],; dp[i][j-1]\right) + a_{ij}, \quad \text{for } i, j \ge 1 ] with the appropriate initialization for the first row and first column. Your solution should compute (dp[N-1][M-1]) for each test case.

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. This is followed by (N) lines, each containing (M) space-separated integers denoting the grid.

outputFormat

For each test case, output a single integer on a new line representing the minimum energy cost to travel from the top-left to the bottom-right corner.## sample

1
1 1
42

42