You're given a matrix $$$A$$$ of size $$$N * M$$$, consisting of integers satisfying $$$|A_{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 block $$$(1, 1)$$$ to block $$$(N, M)$$$ and can only move to the right or downward. 2 paths made by the 2 players can only have $$$(1, 1)$$$ and $$$(N, M)$$$ as two common blocks. 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 numbers $$$N$$$ and $$$M$$$.
Next $$$N$$$ lines consist of $$$M$$$ integers describing the matrix $$$A$$$. Note that $$$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
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.