Tamta 和 Anna 是姐妹，她们喜欢玩“点格棋”（Dots and Boxes）游戏。

游戏开始时，棋盘上有一个 $N+1$ 行 $N+1$ 列的点阵（对应一个 $N \times M$ 的方格网）。玩家轮流在两个未连接的相邻点之间添加一条水平或垂直边（如果两点间距离为 1，则称它们相邻）。如果一名玩家在她的回合中补全了一个 $1 \times 1$ 方格的第四条边，她就占领该方格，获得一分，并再次获得一个回合；否则，轮到另一名玩家。当无法再添加边时，游戏结束。

Anna 和 Tamta 已经玩了一段时间，你注意到在当前状态下，每个方格恰好有零条或两条未连接的边，且现在轮到 Anna 行动。（你可以在右侧图片中看到一个例子。注意，上面的图片并不符合此描述）。

游戏的得分计算公式为 $S_A - S_T$，其中 $S_A$ 是 Anna 从当前状态开始获得的得分，$S_T$ 是 Tamta 获得的得分。显然，Anna 试图最大化该分数，而 Tamta 试图最小化它。你需要计算在双方均采取最优策略情况下的最终得分。

输入格式

第一行包含两个整数 $N$ 和 $M$，分别表示方格网的行数和列数。

接下来的 $N+1$ 行，每行包含 $M$ 个数字（0 或 1，无空格分隔），第 $i$ 行的第 $j$ 个数字为 1 当且仅当坐标为 $(i, j)$ 和 $(i, j+1)$ 的点之间存在一条水平边。

随后的 $N$ 行，每行包含 $M+1$ 个数字，格式相同，第 $i$ 行的第 $j$ 个数字为 1 当且仅当坐标为 $(i, j)$ 和 $(i+1, j)$ 的点之间存在一条垂直边。

输出格式

仅输出一行，包含一个整数，即最终得分。

数据范围

• $3 \le N, M \le 20$
• 每个方格恰好有零条或两条未连接的边

子任务

我们将“连通分量”定义为网格中未被占领的方格构成的最大集合，使得你可以通过遍历尚未绘制的边从一个方格移动到任何其他方格。在下图中，你可以看到 5 个不同的连通分量。

1. (20 分)：游戏中只剩下一个连通分量。
2. (20 分)：$N \cdot M \le 12$。
3. (20 分)：游戏中只剩下两个连通分量。
4. (20 分)：$N \le 7, M \le 7$。
5. (20 分)：无附加限制。

样例

输入格式 1

3 3
000
111
011
110
1010
1000
1001

输出格式 1

-5

输入格式 2

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

输出格式 2

6

说明

第一个样例以及一种可能的最优移动顺序描绘如下（边上的数字表示移动顺序，红色表示 Anna 的移动，蓝色表示 Tamta 的移动）。第二个样例即为上述图片中展示的情况。