tag

轮廓线+状态设计

hint

数据范围很小，状态设计巧妙的话其总数能够接受

背景

在程式之岛上，咩啊是一名曾经的编程语言，现在已被黑暗所控制。他擅长创造出令人毛骨悚然的界面和交互体验。

小基是一名年轻且天真的小编程语言，她来到程式之岛寻求咩啊的帮助。然而，当她抵达时，发现咩啊已被一种名为里海的可怕病毒所感染。

里海是一种能够让编程语言们失去理智和控制力的病毒，它通过暗示和诱惑来操纵其受害者。咩啊已经完全陷入了里海的掌控之中，他开始创造出一种新的界面，一个充满了恐怖和不吉利的世界。

题目描述

程式之岛恢复了往日的宁静与和谐。

图书馆中间有一潭水池，水池中间有一块棋盘，小基和咩啊打算在这里下棋。

棋盘是一张 $n\times m$ 的格点图，每个格子有两个非负的权值 $a_{i,j},b_{i,j}$ 。

小基先手，小基在 $(i,j)$ 格落子会使里海海拔升高 $a_{i,j}$ 。

咩啊后手，咩啊在 $(i,j)$ 格落子会使里海海拔降低 $b_{i,j}$ 。

小基和咩啊喜欢贴贴，所以落子时上面一格和左边一格都不会未落子，当然每个格子只能落一颗子。

小基想要让里海海拔尽量高，咩啊想要让里海海拔尽量低。

小基和咩啊都会采用最优策略，请你预测出最终里海的海拔会变化多少。

输入

第一行有两个整数 $n,m\ (1\le n,m \le 10)$，分别表示棋盘的行数和列数。

第 $2$ 到第 $n + 1$ 行，每行 $m$ 个整数，第 $i + 1$ 行的第 $j$ 个整数表示 $a_{i, j}\ (0\le a_{i,j}\le 10^5)$ 。

第 $n + 2$ 到第 $2n + 1$ 行，每行 $m$ 个整数，第 $n + 1 + i$ 行的第 $j$ 个整数表示 $b_{i, j}\ (0\le b_{i,j}\le 10^5)$ 。

输出

输出一行一个整数，表示最终里海海拔的变化值。

样例

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

2

双方都采用最优策略时，棋局如下：

• 小基下在第 $1$ 行第 $1$ 列。
• 咩啊下在第 $1$ 行第 $2$ 列。
• 小基下在第 $2$ 行第 $1$ 列。
• 咩啊下在第 $1$ 行第 $3$ 列。
• 小基下在第 $2$ 行第 $2$ 列。
• 咩啊下在第 $2$ 行第 $3$ 列。
• 棋盘填满，游戏结束。

小基使海拔升高 $2 + 9 + 1 = 12$，咩啊使海拔降低 $7 + 2 + 1 = 10$。

5 5
69957 90847 86904 93073 40245
28329 60126 87118 6014 47716
44211 82632 7048 25316 18026
35996 66957 93148 28942 76653
24567 48573 21080 27648 79677
39142 22319 55890 94565 5578
43866 63511 78176 77389 67802
3878 89158 53308 62879 79293
72274 15472 6456 52791 12740
79970 46577 95439 33488 75518

32290

来源

2025 UESTC ICPC Training for Dynamic Programming and Search