Mario and the Parallel World

Time limit3sMemory limit1024 MB

Summary

Given a grid of positive integers, find the best right-or-down path sum from top-left to bottom-right when an adversary blocks one cell to minimize that best sum.

Level: Medium7 of 10
Topics: Dynamic programming, Matrix, Implementation
Solved: No attempts yet

Problem

One day Mario and Luigi moved into a parallel world. It is an $n$ by $m$ matrix, and each cell contains a positive integer. Mario's goal in this world is to walk from the top left corner to the bottom right corner and collect as many points as possible. In one step, Mario can move to the adjacent cell on the right or below his current position, if that cell exists.

Mario's score for a route is the sum of the numbers in the cells he visits. Luigi recently fell out with Mario and wants to get in his way. He can occupy one cell of the field other than the top left and bottom right corners, and then Mario cannot pass through that cell. Luigi picks the cell so that Mario, choosing the best route under the new conditions, scores as little as possible.

Find the score Mario gets with his optimal route when Luigi also plays optimally to make Mario's result as bad as possible. It is guaranteed that wherever Luigi stands, Mario can still get from the top left corner to the bottom right corner.

Input

The first line contains two integers $n$ and $m$ , the length and width of the field ( $2 \le n,m \le 1500$ ).

Each of the next $n$ lines contains $m$ integers. The $j$ -th number in the $i$ -th line, $a_{i,j}$ , is the number written in that cell ( $1 \le a_{i,j} \le 10^9$ ).

Output

Print one integer: the score Mario gets with the optimal route when Luigi also acts optimally.

Hint

In the first test from the statement, the optimal choice is for Luigi to take the 3rd cell of the 2nd row. Then Mario can score at most 17 points.

Examples1

Example 1
Input
```
4 4
1 2 3 4
2 1 3 1
3 2 3 5
1 3 4 1
```
Expected output
```
17
```