Maximum Strength Path

Given a 2D grid of integers representing strength values, find the maximum strength path from the top-left corner to the bottom-right corner. You can move only to the right or down. The recurrence used in the dynamic programming solution is given by: \(dp_{i,j} = \max(dp_{i-1,j}, dp_{i,j-1}) + grid[i][j]\), where \(dp_{i,j}\) is the maximum strength accumulated up to cell \((i,j)\). This problem requires handling multiple test cases.

inputFormat

The first line contains an integer \(T\), the number of test cases. Each test case begins with a line containing two space-separated integers \(M\) and \(N\) denoting the number of rows and columns of the grid. This is followed by \(M\) lines, each with \(N\) space-separated integers representing the grid's values.

outputFormat

For each test case, output a single line containing the maximum strength path (i.e. the maximum sum) from the top-left corner to the bottom-right corner of the grid.

2
3 3
1 2 3
4 5 6
7 8 9
2 2
5 3
1 7

29
15