问题1911--跳格子

1911: 跳格子

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 128 MB

题目描述

在那个没有手机电脑的年代,有一种古老的游戏--跳格子。 

在地上画一些方格,每个方格都标记一个数字,选手用单脚跳到方格中,就能获得相应的分数,但不能重复获得。 

小 A 了解到这个游戏后,对这个游戏进行了升级: 

1、在地上画一个由 n * m 个小方格组成的矩阵,行为 n,列为 m,并为每个方格标记一个数字作为分数。 

2、选择两名选手分别从左上角和右上角(第一行的两端)开始比赛,每位选手都可以在不出界的前提下,往左下方,下方,右下方三个方向跳到下一个方格。 

3、最终跳到最后一行,结束游戏,游戏得分为两名选手所经过的方格的分数之和,包括起点和终点,如果两人到达同一方格,只能获取一次分数。 

小 A 邀请小 C 一起参加游戏,请你帮他们计算一下,他们能获得的最高得分是多少。

输入

第一行,整数 n 和 m,表示行和列。 

接下来 n 行,每行 m 个整数,分别表示每个方格的分数。

输出

一个整数,即最高得分。

样例输入 Copy

4 3
1 5 3
2 5 4
1 2 3
3 1 1

样例输出 Copy

22

提示

样例解析: 

小 A 从左上角出发,跳了 1 + 5 + 2 + 3 = 11 分。 

小 C 从右上角出发,跳了 3 + 4 + 3 + 1 = 11 分。 


数据范围: 

2 <= n, m <= 100。 

0 <= 方格分数 <= 100。

来源/分类