P6855 "EZEC-4.5" Walking on a Grid

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.

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

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

[Large sample](https://www.luogu.com.cn/paste/aeqswjyj). 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