ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

1035. Cross-stitch

Time limit: 0.5 second
Memory limit: 64 MB
Problem illustration
Archaeologists have found a cloth decorated with needlework. This needlework is a cross-stitch made with several threads. The following rules have been observed:
  1. The cloth has a grid with square cells.
  2. Each stitch covers a diagonal of one cell of the grid. Stitches can lie on both sides of the cloth, but each of them lies only at one side of the cloth (the thread can start, finish and cross the cloth only at the grid vertices).
  3. At most one stitch can lie on each diagonal of each cell at each side of the cloth.
  4. Each thread makes up several stitches arranged alternately at different sides of the cloth. (It means that two consecutive stitches formed by one thread lay at the different sides of the cloth and are connected in the grid vertex)
  5. A needle can go through the cloth only in the vertexes of the grid.
On the figure you can see an example of a pattern made with six stitches. The grid has size 4 × 5. The face of the cloth is drawn on the upper half of the figure. The stitches lying on the face are drawn with solid lines. The rear stitches uncovered with those of the face are drawn with dot-lines. On the lower half of the figure the cloth is oriented as on the upper half. All the rear stitches are drawn with solid lines there. The face stitches, which do not cover rear stitches, are drawn with dot-lines. This cross-stitch cannot be made with less than four threads.
Archaeologists want to know if the pattern was made with the least number of threads. You have to write a program, which will determine the minimal number of threads needed to make the given pattern.


The first line contains integers N and M that are vertical (N) and horizontal (M) sizes of the grid (1 ≤ N, M ≤ 200). Each of the following 2N lines contains M symbols. Each symbol describes one square of the grid. The first N lines correspond to the face of the cloth and the last N lines correspond to the rear of the cloth. The symbols used are “.”, “/”, “\” and “X” (a dot means an empty square).
For more information see the sample. It corresponds to the cloth drawn at the figure.


Output the minimal number of threads needed to make the described pattern.


4 5
Problem Author: Pavel Zaletsky
Problem Source: Ural Collegiate Programming Contest '99