Description

The jungle you face can be modeled as a grid with $n$ rows and $m$ columns. The cell in row $i$ and column $j$ represents a region. Each cell has an integer weight $v(i,j)$ (possibly negative), representing the gain or cost of visiting that region. Each cell can be visited at most once, and you may not go outside the grid. You are required to start from the cell in the first row and first column, and finish at the cell in the $n$-th row and $m$-th column. Your goal is to maximize the sum of the weights of all visited cells.

Because of certain reasons, your expedition route is subject to some restrictions. Initially you are at the start. Then, on each day, you must first choose one direction among up, down, left, and right, and move $0$ steps (i.e., do not move) or any number of steps along this direction; after that, choose a direction again (it can be the same as before or different), and keep moving along that direction until you reach some boundary position of the grid, ending that day's expedition. The expedition can last for any number of days. The boundary position where a day's expedition ends will be the starting position of the next day, unless that day is the end of the expedition. Note that, because each cell can be visited at most once and your final ending point must be at position $(n,m)$, you need to plan each day's route carefully.

You want to know, under the optimal plan, how large the total gain of the entire expedition can be, that is, the maximum possible sum of the weights of all visited cells.

Input Format

The first line contains two integers, representing the total number of rows $n$ and the total number of columns $m$. Then follow $n$ lines, each containing $m$ integers. The integer in row $i$ and column $j$ corresponds to the gain or cost of visiting the region at row $i$ and column $j$.

Output Format

Output a single integer, the sum of the weights of all visited cells in an optimal expedition route.

10 10
+1 +1 +1 +1 +1 -1 -1 -1 -1 -1
-1 -1 +1 +1 +1 -1 -1 -1 -1 -1
-1 -1 +1 +1 +1 +1 +1 +1 +1 +1
+1 +1 +1 +1 -1 -1 -1 -1 -1 +1
+1 -1 -1 +1 -1 -1 -1 -1 -1 +1
+1 +1 +1 +1 -1 -1 -1 -1 -1 +1
+1 +1 +1 +1 +1 +1 +1 +1 +1 +1
+1 -1 -1 -1 -1 -1 -1 -1 -1 -1
+1 +1 +1 +1 -1 +1 +1 +1 +1 +1
-1 -1 -1 +1 +1 +1 -1 -1 -1 +1

53

Hint

Constraints: For all testdata, $3 \le n \le 800$ and $3 \le m \le 800$. The absolute value of each gain or cost is at most $100000$.

Translated by ChatGPT 5