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 <= n <= 10^3$
$1 <= m <= 10^3$
$1 <= h e i g h t (i, j) <= 10^5$
A single integer, the maximum style points that can be obtained by the pair.
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.
## Input
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 <= n <= 10^3$$1 <= m <= 10^3$$1 <= h e i g h t (i, j) <= 10^5$
## Output
A single integer, the maximum style points that can be obtained by the pair.
[samples]
## Note
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.
**Definitions**
Let $ n, m \in \mathbb{Z}^+ $ denote the number of rows and columns of the grid.
Let $ H = (h_{i,j})_{1 \le i \le n, 1 \le j \le m} $ be the height matrix, where $ h_{i,j} \in \mathbb{Z}^+ $ is the height at position $ (i,j) $.
Michael starts at some position $ (1, j_M) $ with $ 1 \le j_M \le m $, and moves from $ (i, j) $ to $ (i+1, j') $ where $ j' \in \{j-1, j, j+1\} $, until reaching row $ n $.
Trevor starts at some position $ (i_T, 1) $ with $ 1 \le i_T \le n $, and moves from $ (i, j) $ to $ (i', j+1) $ where $ i' \in \{i-1, i, i+1\} $, until reaching column $ m $.
They must meet at least once at some position $ (i, j) $ at the same time step $ t $, meaning:
- Michael reaches $ (i, j) $ at step $ i - 1 $ (since he moves down $ i-1 $ times from row 1),
- Trevor reaches $ (i, j) $ at step $ j - 1 $ (since he moves right $ j-1 $ times from column 1),
- Thus, $ i - 1 = j - 1 \Rightarrow i = j $.
So they can only meet on the diagonal $ i = j $.
**Constraints**
1. $ 1 \le n, m \le 10^3 $
2. $ 1 \le h_{i,j} \le 10^5 $
3. Michael’s path: $ (1, j_0) \to (2, j_1) \to \dots \to (n, j_{n-1}) $, with $ |j_{k} - j_{k-1}| \le 1 $
4. Trevor’s path: $ (i_0, 1) \to (i_1, 2) \to \dots \to (i_{m-1}, m) $, with $ |i_{k} - i_{k-1}| \le 1 $
5. There exists $ k \in \{1, \dots, \min(n,m)\} $ such that $ j_{k-1} = i_{k-1} = k $ (i.e., they meet at $ (k,k) $)
**Objective**
Maximize the total style points:
$$
\max_{\substack{\text{Michael's path } P_M \\ \text{Trevor's path } P_T \\ \text{with } \exists k: P_M(k) = P_T(k) = (k,k)}} \left( \sum_{(i,j) \in P_M} h_{i,j} + \sum_{(i,j) \in P_T} h_{i,j} \right)
$$
Note: If $ (k,k) $ is visited by both, $ h_{k,k} $ is counted twice.