题目描述

有 $n\times m$ 的方格矩阵，小 A 从 $(1,1)$ 出发到 $(n,m)$ ，只能向下或向右走，获得的分数为他经过方格的权值之和。

已知每个方格 $(i,j)$的权值 $a_{i,j}$，你可以将其中任意一个方格上的权值变为 $0$，求变化后小 A 最多能获得分数的最小值。

输入格式

第一行两个整数 $n,m$。

下面 $n$ 行每行 $m$ 个整数 $a_{i,j}$

输出格式

一个整数表示变化后小 A 最多能获得分数的最小值。

2 2
3 3 
6 4

9

3 3
1 1 1
2 1 2
3 1 1

6

提示

大样例

本题使用捆绑测试。

【样例解释】：

样例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$。