84420 - 二维网格游戏
时间限制 : 1 秒
内存限制 : 128 MB
男孩和女孩在被划分成n行m列的二维网格中玩游戏。其中第i行j列的网格中积分a_{i,j}分。
男孩从网格（1，1）出发移动到（n,m)，每次移动只能向右或者向下移动一个网格。
女孩从往（n,1)出发移动到（1，m），每次移动只能向左或者向上移动移动一个网格。
男孩和女孩可以获得经过网格的所有得分。求两个人总计最多能获得多少得分
输入
第一行包含两个数字n、m
接着n行，每行m列。表示每个网格的得分
输出
两个人总计最多能获得多少得分
样例
输入
4 4 2 6 5 3 8 3 8 8 3 9 6 7 5 1 5 6
输出
74
输入
5 5 2 -6 0 -4 -9 6 6 4 -1 -1 5 4 2 0 -4 5 -2 8 3 -1 -2 5 -5 7 -8
输出
32
提示
男孩沿绿色线移动，女孩沿红色线移动。其中共同经过的(2,2)网格只计算一次
5 \leq n,m \leq 500 ,|a_{i,j}| \leq 10^3
来源
原创