题目描述

奶牛们制作了一些藏有金币的馅饼，并把它们排成了一个 $r$ 行 $c$ 列的矩阵。现在，你需要从坐标为 $(1,1)$ 的馅饼旁移动到坐标为 $(r,c)$ 的馅饼旁。对于每次移动，你必须向右移动一列，并且行数的变动不能超过 $1$。即如果你处于坐标为 $(x,y)$ 的馅饼旁，你只能移动到坐标为 $(x-1,y+1)$，$(x,y+1)$ 或 $(x+1,y+1)$ 的馅饼旁。在一个馅饼旁停留时，你可以拿走其中所有的金币。当然，你一定不愿意中途离开矩阵而放弃这些金币。

奶牛们把标有矩阵中每一块馅饼所藏金币数的表格交给了你。你想知道按照以上规则，自己最多能拿到多少金币。

输入格式

第一行两个整数 $r,c$。

接下来 $r$ 行，每行 $c$ 个整数，表示矩阵中每一块馅饼所藏金币数 $t$。

输出格式

一行，一个整数，表示你能拿到的最大金币数。

3 7
6 5 3 7 9 2 7
2 4 3 5 6 8 6
4 9 9 9 1 5 8

50

提示

【数据范围】

对于 $100\%$ 的数据，$1\le r,c\le 100$，$1\le t\le 25$。

【样例说明】

样例给出的矩阵如图所示。

这是一种合法的移动方式。你可以拿到 $47$ 枚金币。

在这个矩阵中你最多能拿到 $50$ 枚金币，路线如图所示。