Description

The cloth is an $n \times m$ grid. The thread can pass from one side of the cloth to the other only at the grid vertices. Each segment of thread covers one of the two diagonals of a unit cell, and during stitching, two consecutive segments within a single stitch must lie on opposite sides of the cloth. Given the patterns on both sides of the cloth (solid lines indicate a thread on this side, dashed lines indicate a thread on the opposite side), determine the minimum number of stitches needed to complete the embroidery. A stitch is a single embroidery process during which the needle does not leave the fabric.

Input Format

The first line contains two numbers $N$ and $M$ ($1 \le N, M \le 200$).

The next $N$ lines each contain $M$ characters describing the front side.

The following $N$ lines each contain $M$ characters describing the back side.

Each cell is represented as follows:

• $\verb!.!$ means empty.
• $\verb!/!$ means a thread from the top-right corner to the bottom-left corner.
• $\verb!\!$ means a thread from the top-left corner to the bottom-right corner.
• $\verb!X!$ means the two diagonals cross.

Output Format

Output a single integer, the minimum number of stitches required.

4 5
.....
.\...
..\..
.....
.....
....\ 
.\X..
.....

4

Hint

Translated by ChatGPT 5