题目描述

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

输入格式

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

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

数据范围

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

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

输出格式

一个整数，表示蜗牛最多可以拿走的宝藏数。

样例

2 2
1 4
2 3

5