You're given a matrix A$A$ of size $N * M$, consisting of integers satisfying $|A[i][j]| <= 100_{i,j}| \leqslant 100$. Rows are numbered $1$ to $N$ downward, and columns are numbers $1$ to $N$ from left to right. There are 2 players, each one will move from point block $(1, 1)$ to point block $(N, M)$ and can only move to the right or downward (A[1][1] = A[N][M] = 0). 2 paths made by the 2 players can only have $(1, 1)$ and $(N, M)$ as two common pointblocks. All other points in the 2 paths must be distinct. Find the 2 paths that have maximum sum.↵
↵
**Input:** the first line consists of 2 numbersare N and M.$N$ and $M$.↵
↵
NextN$N$ lines consist of M$M$ integers describing the matrix A$A$. Note that A[1][1] = A[N][M]$A_{1,1} = A_{N,M} = 0$.↵
↵
**Output:** The maximum sum of the 2 paths.↵
↵
**Example Input:**↵
↵
3 3↵
↵
0 2 3↵
↵
4 5 6↵
↵
7 8 0↵
↵
**Example Output:↵
32**↵
↵
32↵
↵
This problem was included in an offline contest that I participated yesterday. Other contestants said that this is a DP problem but I couldn't figure out the solution.
↵
**Input:** the first line consists of 2 numbers
↵
Next
↵
**Output:** The maximum sum of the 2 paths.↵
↵
**Example Input:**↵
↵
3 3↵
↵
0 2 3↵
↵
4 5 6↵
↵
7 8 0↵
↵
**Example Output:
32
↵
32↵
↵
This problem was included in an offline contest that I participated yesterday. Other contestants said that this is a DP problem but I couldn't figure out the solution.