P1016

[Usaco2006 Oct]Cow Pie Treasures 馅饼里的财富

[Usaco2006 Oct]Cow Pie Treasures 馅饼里的财富

最近，奶牛们热衷于将金币包在面粉中，再烤成馅饼。每块馅饼中含有 NiN_i 枚金币，金币数量被醒目地标记在馅饼表面。

奶牛们将所有馅饼排列成一个 RR 行 CC 列的矩阵。你最初站在坐标为 (1,1)(1,1) 的馅饼旁，并可以拿走其中的所有金币。你需要穿过草地，最终停在坐标为 (R,C)(R,C) 的馅饼旁。

每次移动时，你必须前往下一列，且行坐标的变化不能超过 11。也就是说，如果你当前位于坐标 (r,c)(r,c)，下一步可以移动到以下仍在矩阵范围内的位置之一：

(r−1,c+1),(r,c+1),(r+1,c+1)(r-1,c+1),\quad (r,c+1),\quad (r+1,c+1)

每当你经过一块馅饼时，都可以拿走其中的所有金币。移动过程中不能离开矩阵，并且最终必须到达 (R,C)(R,C)。

给定每块馅饼中金币的数量，请计算按照上述规则最多能够获得多少枚金币。

输入格式

第一行包含两个以空格分隔的整数 RR 和 CC，分别表示馅饼矩阵的行数和列数。

接下来 RR 行，每行包含 CC 个以空格分隔的正整数，依次表示该行从左到右每块馅饼中的金币数量。

输出格式

输出一个正整数，表示最多能够收集到的金币数量。

样例输入

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

样例输出

50

数据范围

  • 1≤R≤C≤1001\le R\le C\le 100；
  • 对于每块馅饼，1≤Ni≤251\le N_i\le 25。

来源与许可

本题为 USACO 2006 October 试题「馅饼里的财富」，题面与测试数据整理自 BZOJ。

样例 1

输入

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

输出

50