P4363 [九省联考 2018] 一双木棋 chess

菲菲和牛牛在一块 $n$ 行 $m$ 列的棋盘上下棋，菲菲执黑棋先手，牛牛执白棋后手。 棋局开始时，棋盘上没有任何棋子，两人轮流在格子上落子，直到填满棋盘时结束。 落子的规则是：一个格子可以落子当且仅当这个格子内没有棋子且这个格子的左侧及上方的所有格子内都有棋子。 棋盘的每个格子上，都写有两个非负整数，从上到下第 $i$ 行中从左到右第 $j$ 列的格子上的两个整数记作 $a_{i,j}$ 和 $b_{i,j}$。 在游戏结束后，菲菲和牛牛会分别计算自己的得分：菲菲的得分是所有有黑棋的格子上的 $a_{i,j}$ 之和，牛牛的得分是所有有白棋的格子上的 $b_{i,j}$ 的和。 菲菲和牛牛都希望，自己的得分减去对方的得分得到的结果最大。现在他们想知道，在给定的棋盘上，如果双方都采用最优策略且知道对方会采用最优策略，那么，最终的结果如何？

无

无

### 样例 1 说明  棋盘如图所示，双方都采用最优策略时，棋局如下： - 菲菲下在第 $1$ 行第 $1$ 列（这是第一步时唯一可以落子的格子）。 - 牛牛下在第 $1$ 行第 $2$ 列。 - 菲菲下在第 $2$ 行第 $1$ 列。 - 牛牛下在第 $1$ 行第 $3$ 列。 - 菲菲下在第 $2$ 行第 $2$ 列。 - 牛牛下在第 $2$ 行第 $3$ 列（这是这一步时唯一可以落子的格子）。 - 填满棋盘，游戏结束。 盘面如下：  菲菲的得分为 $2 + 9 + 1 = 12$，牛牛的得分为 $7 + 2 + 1 = 10$。 ### 数据规模与约定 各测试点信息如下表。  - 对于编号为奇数的测试点，保证 $b_{i, j} = 0$。 - 对于全部的测试点，保证 $1 \leq n, m \leq 10$，$0 \leq a_{i, j}, b_{i, j} \leq 10^5$。