题目描述

贪吃蛇来到了一个神秘的地方，这个地方是个矩形，划分成了 $n$ 行 $m$ 列的格子状，每个格子里有一定重量的食物。贪吃蛇希望自己经过的格子食物重量越来越多，也就是下一次格子里的食物重量一定比这一次格子里的食物重量要多，否则贪吃蛇就会停止移动。当然如果贪吃蛇走到了最下面一行或者最右边一列也会停止移动。贪吃蛇可以自由选择从哪个格子开始，但每次移动只能向下或者向右移动，它想知道最多可以吃掉多少重量的食物？

输入格式

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

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

数据范围

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

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

输出格式

一个整数，表示贪吃蛇最多可以吃掉的食物重量。

样例

3 3
1 4 5
2 3 1
5 1 3

10