在那个没有手机电脑的年代,有一种古老的游戏--跳格子。
在地上画一些方格,每个方格都标记一个数字,选手用单脚跳到方格中,就能获得相应的分数,但不能重复获得。
小 A 了解到这个游戏后,对这个游戏进行了升级:
1、在地上画一个由 n * m 个小方格组成的矩阵,行为 n,列为 m,并为每个方格标记一个数字作为分数。
2、选择两名选手分别从左上角和右上角(第一行的两端)开始比赛,每位选手都可以在不出界的前提下,往左下方,下方,右下方三个方向跳到下一个方格。
3、最终跳到最后一行,结束游戏,游戏得分为两名选手所经过的方格的分数之和,包括起点和终点,如果两人到达同一方格,只能获取一次分数。
小 A 邀请小 C 一起参加游戏,请你帮他们计算一下,他们能获得的最高得分是多少。
第一行,整数 n 和 m,表示行和列。
接下来 n 行,每行 m 个整数,分别表示每个方格的分数。
4 3
1 5 3
2 5 4
1 2 3
3 1 1
22
样例解析:
小 A 从左上角出发,跳了 1 + 5 + 2 + 3 = 11 分。
小 C 从右上角出发,跳了 3 + 4 + 3 + 1 = 11 分。
数据范围:
2 <= n, m <= 100。
0 <= 方格分数 <= 100。