有 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) 的权值变为 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。

对于 100\% 的数据：1\le n,m\le 2\times 10^3,1\le a_{i,j} \le 10^9。

luogu