题目背景

小 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。