P6855 「EZEC-4.5」走方格

有 $n\times m$ 的方格矩阵，小 A 从 $(1,1)$ 出发到 $(n,m)$ ，只能向下或向右走，获得的分数为他经过方格的权值之和。 已知每个方格 $(i,j) $的权值 $a_{i,j}$，你可以将其中任意一个方格上的权值变为 $0$，求变化后小 A 最多能获得分数的**最小值**。

无

无

[大样例](https://www.luogu.com.cn/paste/aeqswjyj) ### 本题使用捆绑测试。 ### 【样例解释】： 样例1： 将 $(2,2)$ 的权值变为 $0$，路径为 $(1,1) $ -> $(2,1) $ ->$(2,2)$ ，获得分数为 $3+6+0=9$。 样例2： 将 $(2,1)$ 的权值变成 $0$，路径为 $(1,1) $ -> $(2,1) $ ->$(3,1)$ ->$(3,2)$ ->$(3,3)$ ，获得分数为 $1+0+3+1+1=6$。 ### 【数据范围】： $Subtask1(40分):1\le n,m \le 100$。 $Subtask2(30分):1\le n,m \le 500$。 $Subtask3(30分):1\le n,m \le 2 \times 10^3$。 对于 $100\%$ 的数据：$1\le n,m\le 2\times 10^3,1\le a_{i,j} \le 10^9$。