[USACO06OCT] Cow Pie Treasures G

题目描述

奶牛们制作了一些藏有金币的馅饼,并把它们排成了一个 $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$。

输出格式


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

输入输出样例

输入样例 #1

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

输出样例 #1

50

说明

**【数据范围】** 对于 $100\%$ 的数据,$1\le r,c\le 100$,$1\le t\le 25$。 ------------ **【样例说明】** ![](https://cdn.luogu.com.cn/upload/image_hosting/pgw19uqm.png) 样例给出的矩阵如图所示。 ![](https://cdn.luogu.com.cn/upload/image_hosting/hwhzq9oy.png) 这是一种合法的移动方式。你可以拿到 $47$ 枚金币。 ![](https://cdn.luogu.com.cn/upload/image_hosting/sdyxlpv5.png) 在这个矩阵中你最多能拿到 $50$ 枚金币,路线如图所示。