2257: 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。

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

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

50