Dots and Boxes Endgame

Consider a game played on a grid of points. Initially, you are given an $(N+1)\times(M+1)$ array of grid points. The grid cells are defined by the adjacent lattice points so that there are exactly $N\times M$ cells. In the game of Dots and Boxes the players take turns drawing a line between two adjacent grid points (horizontally or vertically). When a move completes a cell (i.e. all four edges of a cell are drawn), that cell is awarded to the player and the player makes another move; otherwise, the turn passes to the other player.

In this problem, the grid is in a special state. For every cell, the four surrounding edges have either 0 or 2 edges that are undrawn. A cell with 0 missing edges is already completed and does not contribute to the remaining game. A cell with 2 missing edges is still available. Importantly, the two missing edges of an available cell are fixed, and they determine potential connections with adjacent available cells. In particular, if two adjacent cells both miss their common edge then that undrawn edge is shared by them. Connecting these cells in a graph, each available cell becomes a vertex. An edge is placed between two vertices if the corresponding cells share a common undrawn edge (i.e. the corresponding positions in their edge configuration are both 0). Because every available cell has exactly 2 missing edges, every vertex has degree 0, 1 or 2. Consequently, the available cells form a collection of disjoint components and each component is either a path (an open chain) or a cycle (a closed loop).

The game now proceeds with player A to move. Let \(S_A\) and \(S_T\) be the number of cells collected by players A and T respectively from now on. Under optimal play the objective is to maximize the final score difference \(S_A-S_T\) (player A) or minimize it (player T).

It turns out that the final score difference is determined by the structure of the available cells. For each connected component:

• If the component is a single cell (isolated cell), its value is 1.
• If the component is a path (open chain) with \(L\) available cells (with \(L \ge 2\)), its value is \(L-2\).
• If the component is a cycle (closed chain) with \(L\) cells (automatically \(L\ge 3\)), its value is \(L-4\).

The final score difference is the sum of the values of all components. Compute this sum.

Input Format:

The first line contains two integers N and M (1 ≤ N,M ≤ 1000), representing the number of rows and columns of cells respectively. Following this, there are N lines, each containing M strings. Each string is of length 4 and represents the status of the four edges of a cell in the order: top, right, bottom, left. An edge is drawn if the corresponding character is '1' and undrawn if it is '0'. It is guaranteed that each cell is either complete (i.e. "1111") or available (i.e. exactly two of the four characters are '0').

Output Format:

Output a single integer: the final score difference \(S_A-S_T\) assuming both players play optimally.

Explanation: The idea is to construct a graph where each available cell (with exactly two undrawn edges) is a node. For each pair of adjacent available cells, if they both are missing the common edge then an edge is added connecting them. Then, for each connected component, if it forms a path (i.e. there is at least one node with degree not equal to 2 or the number of edges is less than the number of nodes) its value is L-2 (with L=1 giving value 1). If the component forms a cycle (every node has degree 2 and the number of edges equals the number of nodes) its value is L-4. The answer is the sum of the values of all components.

inputFormat

The first line contains two integers N and M.

Then N lines follow. Each line contains M strings separated by spaces. Each string is of length 4 representing the cell configuration in the order: top, right, bottom, left. '1' indicates a drawn edge and '0' indicates an undrawn edge.

outputFormat

Output a single integer — the final score difference S_A - S_T after optimal play.

sample

1 1
1010

1