Background

Little T and Little A are playing a dots-and-boxes game.

Problem Description

First, Little T takes out a sheet of grid paper with $(N+1) \times (M+1)$ lattice points (these points can be indexed from top to bottom and from left to right as the point in row $1 \sim N+1$ and column $1 \sim M+1$). Each point can be connected to its up, down, left, and right neighboring point (if such a point exists). It is easy to see that this forms an $N \times M$ grid of squares. However, the sheet Little T takes out has no edges drawn on it, and the goal of Little T and Little A is to draw line segments between lattice points.

The rules are as follows. In each turn, a player may draw a line segment between two adjacent lattice points. If drawing this segment completes a square, then that square belongs to the player. The player may then continue drawing segments, until the segment they draw does not gain any square, at which point it becomes the next player’s turn. When all players can no longer draw any segment, the game ends.

For example, the following figure shows a possible result of drawing segments when $N=2,M=3$:

The dashed lines are the segments drawn by the player in that turn.

Little A and Little T have been playing for a long time. You notice that their current grid satisfies the following condition: for every square, among its four surrounding edges, there are either $0$ or $2$ edges that have not been drawn yet. For instance, the following figure satisfies the condition. In the previous figure, all cases except the first one also satisfy the condition:

Moreover, it is now exactly Little A’s turn.

Define Little A’s and Little T’s scores $S_A,S_T$ as the points they obtain from now until the end of the game. Then the final score of the whole game is $S_A-S_T$. Little A wants to make this final score as large as possible, while Little T wants the opposite. Both will play optimally according to their goals.

You need to output the final score under optimal play.

Input Format

The first line contains two integers $N,M$, representing the size of the grid paper.

Then there are $N+1$ lines, each containing $M$ integers without spaces, consisting of $0$ and $1$. The $j$-th number in the $i$-th line is $0$ if there is no segment between the point at row $i$, column $j$ and the point at row $i$, column $j+1$, and is $1$ otherwise.

Then there are $N$ lines, each containing $M+1$ integers without spaces, consisting of $0$ and $1$. The $j$-th number in the $i$-th line is $0$ if there is no segment between the point at row $i$, column $j$ and the point at row $i+1$, column $j$, and is $1$ otherwise.

3 3
000
111
011
110
1010
1000
1001

-5

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

6

Hint

Explanation for Sample 1

The following figure shows one possible way to draw segments. Red indicates Little A’s moves, and blue indicates Little T’s moves:

Explanation for Sample 2

This sample is the second figure in the problem statement.

Constraints

This problem uses bundled testdata.

• Subtask 1 (20 pts): The input contains only one connected component.
• Subtask 2 (20 pts): $N \times M \le 12$.
• Subtask 3 (20 pts): The input contains only two connected components.
• Subtask 4 (20 pts): $N,M \le 7$.
• Subtask 5 (20 pts): No additional restrictions.

For $100\%$ of the testdata, $3 \le N, M \le 20$, and for every square, among its four surrounding edges, there are either $0$ or $2$ edges that have not been drawn yet.

A connected component is defined as a region enclosed by already-drawn edges and the boundary of the grid paper. For example, the following figure has $5$ connected components:

Note that squares already owned by a player do not belong to any connected component.

Notes

Translated from eJOI 2020 Day2 C Dots and Boxes.

Translated by ChatGPT 5