407281: GYM102741 I Stunt Jump Escape

Michael and Trevor have just pulled off the biggest heist Los Santos has ever seen! However, they must now escape the cops. In order to evade quickly, they decide to split up and drive dirt bikes across the map. The map is a hilly terrain laid out as a grid. Michael is traveling from the top row of the map to the bottom row, while Trevor is driving from the leftmost column to the rightmost column.

Every minute Michael must move downwards and Trevor must move rightwards. Specifically, Michael can move from position $$$(i, j)$$$ at time $$$t$$$ to either $$$(i+1, j-1)$$$, $$$(i+1, j)$$$ or $$$(i+1, j+1)$$$ at time $$$t+1$$$. Trevor can move from position $$$(i, j)$$$ at time $$$t$$$ to $$$(i-1, j+1)$$$, $$$(i, j+1)$$$ or $$$(i+1, j+1)$$$ at time $$$t+1$$$

To further confuse the cops and help them escape, they decide to meet somewhere along the way and swap vehicles quickly. This means that they must be in the same position at the same time at least once.

Both love pulling off stunts, and for each hill that they drive over, they will get points equal to the height of that hill. Help them maximize their total style points from this journey!

The first line contains 2 space-separated integers $$$n$$$ (the number of rows) and $$$m$$$ (the number of columns). The following $$$n$$$ lines contain $$$m$$$ integers each, denoting the heights of each hill in the grid.

$$$ 1 \le n \le 10^3$$$

$$$ 1 \le m \le 10^3$$$

$$$ 1 \le height(i,j) \le 10^5$$$

A single integer, the maximum style points that can be obtained by the pair.

2 2
1 1
2 2

7

3 3
1 2 3
4 5 6
7 8 9

42

If the starting position is the same, this counts as a 'meeting' and they need not meet again. Also, if they drive over the same hill they both get style points from that hill.