Problem Description

There is an $n \times m$ grid matrix. Little A starts from $(1,1)$ and goes to $(n,m)$. He can only move down or right. The score he gets is the sum of the weights of the cells he passes through.

You are given the weight $a_{i,j}$ of each cell $(i,j)$. You may change the weight of any one cell to $0$. Find the minimum value of the maximum score Little A can obtain after the change.

Input Format

The first line contains two integers $n, m$.

The next $n$ lines each contain $m$ integers $a_{i,j}$.

Output Format

Output one integer, the minimum value of the maximum score Little A can obtain after the change.

2 2
3 3 
6 4

9

3 3
1 1 1
2 1 2
3 1 1

6

Hint

Large sample.

This problem uses bundled testdata.

Sample Explanation

Sample 1: Change the weight of $(2,2)$ to $0$. The path is $(1,1)$ -> $(2,1)$ -> $(2,2)$, and the score is $3 + 6 + 0 = 9$.

Sample 2: Change the weight of $(2,1)$ to $0$. The path is $(1,1)$ -> $(2,1)$ -> $(3,1)$ -> $(3,2)$ -> $(3,3)$, and the score is $1 + 0 + 3 + 1 + 1 = 6$.

Constraints

$Subtask 1(40\ points): 1 \le n, m \le 100$.

$Subtask 2(30\ points): 1 \le n, m \le 500$.

$Subtask 3(30\ points): 1 \le n, m \le 2 \times 10^3$.

For $100\%$ of the testdata: $1 \le n, m \le 2 \times 10^3$, $1 \le a_{i,j} \le 10^9$.

Translated by ChatGPT 5