Problem Description

There is an $n \times m$ grid, and each cell contains an integer. Now there is a little bear that wants to move from the top-left corner to the bottom-right corner. Each step can only move one cell up, down, or right, and it cannot visit any cell more than once, and it cannot go out of bounds. The bear will take all the integers in the cells it passes through. Find the maximum possible sum of the integers it can take.

Input Format

The first line contains two integers $n, m$.

In the next $n$ lines, each line contains $m$ integers, which represent the integer in each cell in order.

Output Format

Output one integer, which is the maximum sum of integers the bear can take.

3 4
1 -1 3 2
2 -1 4 -1
-2 2 -3 -1

9

2 5
-1 -1 -3 -2 -7
-2 -1 -4 -1 -2

-10

Hint

Explanation for Sample 1

Explanation for Sample 2

Constraints

• For $20\%$ of the testdata, $n, m \le 5$.
• For $40\%$ of the testdata, $n, m \le 50$.
• For $70\%$ of the testdata, $n, m \le 300$.
• For $100\%$ of the testdata, $1 \le n, m \le 10^3$. The absolute value of the integers in the grid does not exceed $10^4$.

On 2024/2/4, one set of hack testdata was added.

Translated by ChatGPT 5