Jungle Expedition Maximum Gain

You are given a grid with n rows and m columns. The cell in the i-th row and j-th column has an integer weight \(v(i,j)\) (which may be negative) representing the profit (or cost) you obtain when you visit that cell. You start at the top‐left cell (cell (1,1)) and must finish at the bottom‐right cell (cell (n,m)). Each cell may be visited at most once and you are not allowed to leave the grid boundary.

The expedition is divided into days. On each day, if your starting cell is S, you perform two movement segments:

1. First, you choose one of the four directions (up, down, left, or right) and move in that direction for an arbitrary number of steps (possibly 0 steps). You must remain inside the grid and cannot traverse a cell that has been visited before.
2. Then, from your current position (call it I), you choose a (possibly different) direction and continue moving in that direction until you reach a cell on the border of the grid. (A border cell is one in the first or last row, or in the first or last column.) In this second segment you must take at least one step if I is not already the final destination. All cells traversed must be valid and unvisited.

The cell where you end the day (the border cell reached in the second segment) becomes the starting cell for the next day (unless it is cell (n,m), where the expedition ends). Your overall gain is the sum of the weights of all visited cells (including the starting cell, and each cell is counted only once). Your task is to plan the expedition so as to maximize the total gain.

Note: Any formulas should be written in LaTeX. For example, the total gain is \[ \text{Gain} = \sum_{(i,j) \in \text{visited}} v(i,j). \]

inputFormat

The first line contains two integers n and m (the number of rows and columns in the grid).
The following n lines each contain m integers representing the weight \(v(i,j)\) of each cell.

outputFormat

Output a single integer: the maximum total gain achievable from (1,1) to (n,m) following the movement rules.

sample

2 2
1 2
3 4

8