Minimizing the Maximum Path Score

You are given an $n\times m$ grid. Each cell $(i,j)$ contains a weight $a_{i,j}$. A traveller starts at $(1,1)$ and wants to reach $(n,m)$ by moving only down or right. The score of a path is the sum of the weights of the cells visited.

You are allowed to change the weight of exactly one cell to 0. After that, the traveller will choose a path that maximizes his score (using the new cell values). Your task is to choose the cell to modify so that the maximum score the traveller can obtain is minimized, and output that minimized maximum score.

Note: If the cell you change is not used on every maximum‐scoring path of the original grid, then there exists a path that avoids the modified cell and yields the original maximum score. Hence, only a modification of a cell that is present in every maximum‐scoring path can actually reduce the score.

Let us denote by $dp_1(i,j)$ the maximum sum from $(1,1)$ to $(i,j)$ and by $dp_2(i,j)$ the maximum sum from $(i,j)$ to $(n,m)$ (both computed in the usual way using only right and down moves). Then the overall maximum score is $$S = dp_1(n,m).$$ A cell $(i,j)$ lies on a maximum path if $$dp_1(i,j) + dp_2(i,j) - a_{i,j} = S.$$ Furthermore, by counting the number of ways to achieve these maximum scores (say $cnt_1(i,j)$ and $cnt_2(i,j)$) one may decide whether a cell is mandatory (i.e. appears in every maximum path) if $$cnt_1(i,j) \times cnt_2(i,j) = cnt_1(n,m).$$ For any mandatory cell $(i,j)$, if you change its weight to 0, then any path passing through it will have its score decreased by $a_{i,j}$, i.e. to $S - a_{i,j}$. However, there might be a path that completely avoids $(i,j)$ and whose score (computed on the original grid) remains lower than $S$. Thus, the resulting maximum score after the modification is $$F = \max(S - a_{i,j}, \; S_{alt}),$$ where $S_{alt}$ is the maximum score obtainable by any path that does not visit $(i,j)$. Your goal is to choose a mandatory cell (if one exists) to minimize this value. If no mandatory cell exists, the answer will simply be $S$ because the traveller can avoid the modified cell.

inputFormat

The first line contains two integers $n$ and $m$ ($1 \le n,m \le 500$, for example) — the number of rows and columns.

Then follow $n$ lines, each containing $m$ integers. The $j$-th integer in the $i$-th line denotes $a_{i,j}$, the weight of cell $(i,j)$.

outputFormat

Output a single integer — the minimized maximum score that the traveller can achieve after you change one cell’s weight to 0 optimally.

sample

2 2
1 2
3 4

4