CF46E.Comb

Having endured all the hardships, Lara Croft finally found herself in a room with treasures. To her surprise she didn't find golden mountains there. Lara looked around and noticed on the floor a painted table n × m panels in size with integers written on the panels. There also was a huge number of stones lying by the wall. On the pillar near the table Lara found a guidance note which said that to get hold of the treasures one has to choose some non-zero number of the first panels in each row of the table and put stones on all those panels to push them down. After that she will receive a number of golden coins equal to the sum of numbers written on the chosen panels. Lara quickly made up her mind on how to arrange the stones and was about to start when she noticed an addition to the note in small font below. According to the addition, for the room ceiling not to crush and smash the adventurer, the chosen panels should form a comb. It was explained that the chosen panels form a comb when the sequence _c_1, _c_2, ..., c__n made from the quantities of panels chosen in each table line satisfies the following property: _c_1 > _c_2 < _c_3 > _c_4 < ..., i.e. the inequation mark interchanges between the neighboring elements. Now Lara is bewildered and doesn't know what to do. Help her to determine the largest number of coins she can get and survive at the same time.

历经千辛万苦，劳拉·克罗夫特终于抵达了一间藏有宝藏的密室。令她惊讶的是，这里并没有想象中的金山。劳拉环顾四周，发现地板上有一张绘制好的 $ n \times m $ 面板表格，每个面板上都写有一个整数。墙边还堆着大量石块。在桌旁的一根石柱上，劳拉发现了一张指引字条，上面写道：若想获得宝藏，必须在表格的每一行中，从该行最左侧开始选择至少一个面板，并将石块放置在所有被选中的面板上，将其压下。随后，她将获得与所选面板上数字之和相等数量的金币。劳拉迅速想好了石块的摆放方案，正准备动手时，却注意到字条下方还有一行用小号字体写就的补充说明：为防止密室天花板坍塌并砸伤探险者，所选面板必须构成一把“梳子”（comb）。补充说明进一步解释道：设 $ c_1, c_2, \dots, c_n $ 为各行中所选面板的数量，则这些数量必须满足如下性质：

$$c_1 > c_2 < c_3 > c_4 < \cdots,$$

即相邻元素之间的不等号方向交替变化。
如今劳拉困惑不已，不知如何是好。请帮她确定在确保自身安全的前提下，所能获取的金币数量的最大值。

The first line contains a pair of integers n, m (2 ≤ n, m ≤ 1500). Next n lines contain m integers each — that is the table itself. The absolute value of the numbers in the table does not exceed 10000.

第一行包含一对整数 $n$ 和 $m$（$2 \leq n, m \leq 1500$）。接下来的 $n$ 行，每行包含 $m$ 个整数——即该表格本身。表格中数字的绝对值不超过 $10000$。

Print the single number — the maximum number of coins Lara can get.

输出一个数字—— Lara 能获得的最多硬币数量。