F. Game

时间限制:3s

空间限制:64MB

本题分值:250

题目背景

放課後、西片くんは高木さんと教室で勝負します。

题目描述

现有 \(n\) 行 \(m\) 列的网格，每个格子上写有一个数字 \(a_{ij}\) 。用坐标 \((i,j)\) 表示第 \(i\) 行第 \(j\) 列。

网格的左上角 \((1,1)\) 处有一个棋子。高木和西片两人轮流控制棋子，每次可以选择以下一项之一：

• 将棋子向右移动一格，棋子移动后，将获得 落点处 的数字所对应的分数。
• 将棋子向下移动一格，棋子移动后，将获得 落点处 的数字所对应的分数。

特别地，不能将棋子移动到网格的外部。

当棋子到达右下角 \((n,m)\) 点时，游戏结束。此时通过比较两人得到的分数来决定胜负。

游戏中，西片的策略如下：比较棋子右、下两个格子中的数字，然后走到数字较大的一方。特别地——

• 如果右方格子和下方格子 数字相同，西片会选择 右方的格子。
• 如果棋子已经到达了下边界或右边界，导致某一种方案不可行，西片会选择另一种方案。

高木同学足够聪明，所以她总会选择最优的方案。

高木优先控制棋子，问游戏结束后，高木将比西片多出多少分？（当然，答案是负数也是合理的。）

输入格式

第一行两个正整数 \(n,m\) ，表示网格的大小。

接下来 \(n\) 行每行 \(m\) 个整数。

输出格式

一行一个整数，表示游戏中两人的分数差。

样例输入1

3 3
1 100 10000
15 140 10000 
30 -50 0

样例输出1

9875

样例1解释

路线如下：\((1,1)\to (2,1)\to (2,2)\to (2,3)\to (3,3)\)

获得的分数：\(\color{DeepPink}{15}\) \(\to\) \(\color{Royalblue}{140}\) \(\to\) \(\color{DeepPink}{10000}\) \(\to\) \(\color{Royalblue}{0}\)

所以答案是： \(\color{DeepPink}{15}\) - \(\color{Royalblue}{140}\) + \(\color{DeepPink}{10000}\) - \(\color{Royalblue}{0}\)= 9875

（根据上述规则，起点处的数字是不计入分数的）

样例输入2

10 6
7819 8716 8344 9251 8868 5982 
7004 8278 9713 -3417 -7696 -5404 
-7925 -8297 9591 132 875 -9551 
-846 -1863 119 6381 7431 7212 
-117 5108 -2006 -4333 3023 5318 
2985 -9874 -6073 -1725 -3338 -6627 
-7832 -3950 3524 -598 8581 -6884 
-9643 -8117 -5477 1686 3951 -5574 
-9437 5066 -1038 -5438 2374 7713 
-9176 -2177 -7686 7526 -8497 -7225 

样例输出2

20951

数据范围及限制

网格中的数字 \(-10^9\le a_{ij}\le 10^9\)

测试点编号	\(n,m\)	测试点分值
1~3	\(n=1\) ，\(2\le m\le 10\)	每个测试点10分
4~7	\(2\le n,m\le 10\)	每个测试点15分
8~11	\(n=2\)，\(1\le m\le 1000\)	每个测试点15分
12~16	\(2\le n,m\le 1000\)	每个测试点20分

请注意，最终答案可能 不能 用\(32\)位整数表示。