Problem Description

E869120 and square1001 decided to move through a grid of size $H \times W$ to buy souvenirs.
The top-left cell is the starting point, and the bottom-right cell is the goal.
The cell at the $i$-th row and $j$-th column has $a_{i, j}$ souvenirs for sale.
They decided to cooperate to collect as many souvenirs as possible.
However, they must take the shortest path, or else they will get TLE (Time Limit Exceeded).
Find the maximum number of souvenirs they can buy.

Input Format

The input is given from the standard input in the following format:

$H\ W$ $a_{1,\ 1}\ a_{1,\ 2}\ \cdots\ a_{1,\ W}$ $a_{2,\ 1}\ a_{2,\ 2}\ \cdots\ a_{2,\ W}$ $\vdots\ \vdots\ \vdots$ $a_{H,\ 1}\ a_{H,\ 2}\ \cdots\ a_{H,\ W}$

• The first line contains two integers $H$ and $W$.
• The next $H$ lines contain $W$ integers each, separated by spaces.

Output Format

Output should follow the standard output format:

• Print the maximum number of souvenirs that can be bought in one line.

Sample Input and Output

Sample Input #1

3 3
1 0 5
2 2 3
4 2 4

Sample Output #1

21

Sample Input #2

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

Sample Output #2

97

Notes/Hints

Constraints

• $1 \le H, W \le 200$
• $0 \le a_{i, j} \le 10^5$

Subtasks

Subtask 1 \[50 points\]

• $1 \le H \le 2$

Subtask 2 \[80 points\]
- $1 \le H \le 3$

Subtask 3 \[120 points\]
- $1 \le H, W \le 7$

Subtask 4 \[150 points\]
- $1 \le H, W \le 30$

Subtask 5 \[200 points\]
- No additional constraints.

Sample Explanation 1

Here, the cell at the $i$-th row and $j$-th column is denoted as $(i, j)$. The optimal path is as follows:
- E869120 moves $ (1, 1) -> (1, 2) -> (1, 3) -> (2, 3) -> (3, 3) $.
- square1001 moves $ (1, 1) -> (2, 1) -> (3, 1) -> (3, 2) -> (3, 3) $.
Together, they can buy a total of 21 souvenirs.

见题面 Input 部分

见题面 Output 部分