4478: 「九省联考 2018」一双木棋

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

从标准输入中读入数据。 输入第一行包含两个正整数 $n, m$，保证 $n, m \leq 10$。 接下来 $n$ 行，每行 $m$ 个非负整数，按从上到下从左到右的顺序描述每个格子上的第一个非负整数：其中第 $i$ 行中第 $j$ 个数表示 $A_{i,j}$。 接下来 $n$ 行，每行 $m$ 个非负整数，按从上到下从左到右的顺序描述每个格子上的第二个非负整数：其中第 $i$ 行中第 $j$ 个数表示 $B_{i,j}$。

输出到标准输出中。 输出一个整数，表示菲菲的得分减去牛牛的得分的结果。

2 3
2 7 3
9 1 2
3 7 2
2 3 1

2