# Maximum Coins

Hard
0/120
Average time to solve is 16m

## Problem statement

You are given a two-dimensional matrix of integers of dimensions N*M, where each cell represents the number of coins in that cell. Alice and Bob have to collect the maximum number of coins. The followings are the conditions to collect coins:

Alice starts from top left corner, i.e., (0, 0) and should reach left bottom corner, i.e., (N-1, 0). Bob starts from top right corner, i.e., (0, M-1) and should reach bottom right corner, i.e., (N-1, M-1).

From a point (i, j), Alice and Bob can move to (i+1, j+1) or (i+1, j-1) or (i+1, j)

They have to collect all the coins that are present at a cell. If Alice has already collected coins of a cell, then Bob gets no coins if goes through that cell again.

For example :
``````If the matrix is
0 2 4 1
4 8 3 7
2 3 6 2
9 7 8 3
1 5 9 4

Then answer is 47. As, Alice will collect coins 0+8+3+9+1 = 21 coins. Bob will collect coins 1+7+6+8+4 = 26 coins. Total coins is 21+26 = 47 coins.
``````
Detailed explanation ( Input/output format, Notes, Images )
Constraints:
``````1 <= T <= 5
1 <= N <= 10^2
1 <= M <= 10^2
0 <= MAT[i][j] <= 10^3

Time Limit: 1 sec
``````
##### Sample Input 1:
``````1
5 4
3 6 8 2
5 2 4 3
1 1 20 10
1 1 20 10
1 1 20 10
``````
##### Sample Output 1:
``````73
``````
##### Explanation for Input 1:
``````Alice will collect coins 3 + 2 + 20 + 1 + 1 = 27 coins.
Bob will collect coins 2 + 4 + 10 + 20 + 10 = 46 coins.
So total coins will get connected are 27 + 46 = 73 coins.
``````
##### Sample Input 2:
``````1
4 1
3
6
7
8
``````
##### Sample Output 2:
``````24
``````
##### Explanation for Input 2:
``````As, initially both are at (0,0) so either Alice or Bob can pick up 3 coins. Similarly is the case with every coin. So total 24 coins will get picked.
``````
Console