暂无测试数据。

蜗牛来到了一个神秘的地方，这个地方是个矩形，划分成了 $n$ 行 $m$ 列的格子状，每个格子里有一定数量的宝藏。

蜗牛会选择一个格子开始一直往右走，或者一直往下走，形成一条直线路径，它有点贪心，想要经过的格子里的宝藏数是递增的，也就是下一次在的格子里的宝藏一定要比这一次在的格子里的多。当没办法满足这个条件的时候蜗牛就会停止移动，当然如果蜗牛走到了最下面一行或者最右边一列也会停止移动，蜗牛想知道它最多可以拿走多少宝藏。

输入格式

第一行，两个正整数 $n, m(1 \leq n, m \leq 10 ^ 3)$。

接下来 $n$ 行，每行 $m$ 个正整数 $a_{ij}(1 \leq a_{ij} \leq 10 ^ 9)$ ，分别表示每个格子中宝藏的数量。

输出格式

输出一行，包含一个整数，表示蜗牛最多可以拿走的宝藏数。

数据范围

对于 $60\%$ 的数据，$1 \leq n, m \leq 100, 1 \leq a_{ij} \leq 10 ^ 7$

对于 $100\%$ 的数据，$1 \leq n, m \leq 10 ^ 3, 1 \leq a_{ij} \leq 10 ^ 9$

难度

入门

题号

T2991

2 2
1 4
2 3

5