[eJOI2020 Day2] Dots and Boxes

小 T 和小 A 在玩一种点格游戏。

首先，小 T 拿出了一张拥有 $(N+1) \times (M+1)$ 个格点的方格纸（这些格子从上到下，从左到右可以编号为第 $1 \sim N+1$ 行第 $1 \sim M+1$ 列的格点），每个格点向上下左右的那个格点（如果那个方向有格点的话）连边，不难发现，会形成一个 $N \times M$ 的方格矩阵。但是小 T 拿出的是没有连边的格点方格纸，小 T 和小 A 的目标就是在格点之间连线。 游戏规则是这样的，每一轮玩家可以在两个格点之间连线，如果连完线能连好一个格子，那么这个格子就属于这个玩家了。然后玩家可以继续连线，直到连完线不能获得格子为止，就换到下一个玩家。当所有玩家都不能连线时，游戏结束。 比如下面这张图即为当 $N=2,M=3$ 时两位玩家可能的连线结果：  其中虚线为这一轮玩家连的线。 小 A 和小 T 已经玩了许久了，你发现他们现在的方格纸满足每一个格子周围的四条边都有 **$0$ 条或 $2$ 条未被连线**，比如下面这张图就满足要求，上面这张图除了第一幅图也都满足要求：  并且刚好轮到小 A 了。 定义小 A 和小 T 的分数 $S_A,S_T$ 为玩家从现在开始得到的分数，那么整个游戏的分数即为 $S_A-S_T$，小 A 要让整个游戏的分数变得越大越好，小 T 则反之，他们都会按照他们的目标做最优策略。 你要求出他们做最优策略下得到的分数。

第一行两个整数 $N,M$ 代表方格纸的大小。 接下来 $N+1$ 行每行 $M$ 个 **不用空格隔开的** 整数，包含 $0$ 和 $1$，第 $i$ 行第 $j$ 个数为 $0$ 就代表第 $i$ 行第 $j$ 列的格点与第 $i$ 行第 $j+1$ 列的格点之间没有连线，$1$ 则反之。 接下来 $N$ 行每行 $M+1$ 个 **不用空格隔开的** 整数，包含 $0$ 和 $1$，第 $i$ 行第 $j$ 个数 $0$ 就代表第 $i$ 行第 $j$ 列的格点与第 $i+1$ 行第 $j$ 列的格点之间没有连线，$1$ 则反之。

3 3
000
111
011
110
1010
1000
1001

-5

5 5
00100
10100
11010
00100
01000
11100
011111
001011
101011
110111
100111

6

#### 样例 1 解释 下图为其中一种连线方式，红色为小 A 的操作，蓝色为小 T 的操作：  #### 样例 2 解释 这个样例为题目描述中的第二个图片。 #### 数据规模与约定 **本题采用捆绑测试。** - Subtask 1（20 pts）：给出的输入只包含一个连通块。 - Subtask 2（20 pts）：$N \times M \le 12$。 - Subtask 3（20 pts）：给出的输入只包含两个连通块。 - Subtask 4（20 pts）：$N,M \le 7$。 - Subtask 5（20 pts）：无特殊限制。 对于 $100\%$ 的数据，$3 \le N, M \le 20$，**每一个格子周围的四条边都有 $0$ 条或 $2$ 条未被连线**。 其中一个连通块定义为已连上的边与方格纸的边缘围起来的块，比如说下面这个图有 $5$ 个连通块：  注意已被玩家占有的方格不属于任意一个连通块。 #### 说明 翻译自 [eJOI 2020 Day2 C Dots and Boxes](https://ejoi2020.ge/static/assets/Day2/Problems/Game.pdf)。