Maximum Coins Collection Problem

Imagine a two-dimensional grid with 'N' rows and 'M' columns, where each cell contains a certain number of coins. Alice and Bob want to maximize the total number of coins they collect under the following conditions:

• Alice starts from the top-left corner (0, 0) and must reach the bottom-left corner (N-1, 0).
• Bob starts from the top-right corner (0, M-1) and must reach the bottom-right corner (N-1, M-1).
• From any cell (i, j), they can move to (i+1, j+1), (i+1, j-1), or (i+1, j).
• If Alice collects coins from a cell, Bob cannot collect coins from that specific cell again.

Input:

The first line of the input contains a single integer T, indicating the number of test cases.
For each test case:
The first line contains two integers, 'N' and 'M', separated by a space, indicating the number of rows and columns.
Next, 'N' lines follow, each containing 'M' integers representing the coin values in the grid.

Output:

For each test case, print a single integer representing the maximum number of coins Alice and Bob can collect together.

Example:

Input:
1
5 5
0 2 4 1
4 8 3 7
2 3 6 2
9 7 8 3
1 5 9 4

Output:
47

Explanation: Alice collects 21 coins and Bob collects 26 coins, making the total 47 coins.

Constraints:

• 1 <= T <= 5
• 1 <= N <= 10^2
• 1 <= M <= 10^2
• 0 <= MAT[i][j] <= 10^3
• Time Limit: 1 sec

Note:

You only need to implement the function to solve the problem; printing the result is managed by the system.