[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$ 枚金币,路线如图所示。