#1036. 马话家tyx

内存限制:512 MiB 时间限制:1125 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 丁丁跑卡车

题目描述

众所周知,tyx是一个大马话家,由于马话说的太多,因此tyx本人也逐渐马化。具体表现为,tyx现在走路也只会走马步,就像中国象棋里的马一样,并且他现在热爱吃草。

现在tyx正处在一块巨大的 列的马场上,马场上的每个点 都有一定量的草

作为马话家,tyx自然与一般的马不一样,他每到达一个点,就会将这个点的所有草全吃光,并且他不会重复到达一个点两次。

tyx为了不让自己吃的太多,因此他行进的路线是有讲究的,他的下一个点的草的数量必须要少于当前所在的点上原有的草的数量。当然,tyx还是尽可能的想要多吃一些草,因此他可以任意选择一个点作为他的起点,并规划一条合理的路线。

现在tyx想知道,他最多可以吃到多少草?

输入格式

第一行两个整数 ,表示马场的大小。

接下来 行,每行 个正整数,表示马场上每个点的草的数量

输出格式

输出一行一个整数 ,表示tyx最多能吃到的草的数量。

样例

样例输入1

3 4
4 1 3 2
2 1 2 3
3 5 1 1

样例输出1

11

样例输入2

3 3
1 1 1
1 2 1
1 1 1

样例输出2

2

数据范围与提示

由于读入量较大,请使用较快速的读入方式。