「EZEC-4.5」走方格
题目描述
有 $n\times m$ 的方格矩阵，小 A 从 $(1,1)$ 出发到 $(n,m)$ ，只能向下或向右走，获得的分数为他经过方格的权值之和。
已知每个方格 $(i,j) $的权值 $a_{i,j}$，你可以将其中任意一个方格上的权值变为 $0$，求变化后小 A 最多能获得分数的**最小值**。
输入输出格式
输入格式
第一行两个整数 $n,m$。
下面 $n$ 行每行 $m$ 个整数 $a_{i,j}$
输出格式
一个整数表示变化后小 A 最多能获得分数的**最小值**。
输入输出样例
输入样例 #1
2 2
3 3
6 4输出样例 #1
9输入样例 #2
3 3
1 1 1
2 1 2
3 1 1输出样例 #2
6说明
[大样例](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$。