P6208 [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$。

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

**【数据范围】** 对于 $100\%$ 的数据，$1\le r,c\le 100$，$1\le t\le 25$。 ------------ **【样例说明】**  样例给出的矩阵如图所示。  这是一种合法的移动方式。你可以拿到 $47$ 枚金币。  在这个矩阵中你最多能拿到 $50$ 枚金币，路线如图所示。