Problem Description

Seto, the curator of the Tenkaichi Art Museum, has been tasked with deciding the layout for a new section featuring black and white mosaic art.

To enhance the visual appeal, Seto wants each adjacent piece of art to resemble each other.

Therefore, Seto decided to define the dissimilarity between two pieces of art.

Mosaic art is painted in either white or black on an $M \times N$ grid.

Consider the operation to convert one mosaic art into the other, and the minimum cost required for that operation as the dissimilarity.

The operations include converting a black square to a white square, converting a white square to a black square, and swapping adjacent squares in four directions (up, down, left, right). Each operation costs $ 1 $.

Create a program to calculate the dissimilarity between two given mosaic arts for Seto.

Input Format

The input is given from the standard input in the following format:

$ M $ $ N $ $ A_{1,1} $ $ A_{1,2} $ … $ A_{1,N} $ $ A_{2,1} $ $ A_{2,2} $ … $ A_{2,N} $ : $ A_{M,1} $ $ A_{M,2} $ … $ A_{M,N} $ $ B_{1,1} $ $ B_{1,2} $ … $ B_{1,N} $ $ B_{2,1} $ $ B_{2,2} $ … $ B_{2,N} $ : $ B_{M,1} $ $ B_{M,2} $ … $ B_{M,N} $

• The first line contains the vertical size of the art $ M $ ( $1 \leq M \leq 70$ ) and the horizontal size of the art $ N $ ( $1 \leq N \leq 70$ ) separated by spaces.
• The next $ M $ lines contain the first mosaic art.
  Each line contains $ N $ colors $ A_{i,j} $ separated by spaces.
  If the square at the $ i $-th row and $ j $-th column of the first mosaic art is black, $ A_{i,j} = 0 $. If it is white, $ A_{i,j} = 1 $.
• The next $ M $ lines contain the second mosaic art.
  Each line contains $ N $ colors $ B_{i,j} $ separated by spaces.
  If the square at the $ i $-th row and $ j $-th column of the second mosaic art is black, $ B_{i,j} = 0 $. If it is white, $ B_{i,j} = 1 $.

Output Format

Output the dissimilarity between the two mosaic arts in one line. End the output with a newline.

Sample Input and Output

Sample Input #1

2 2
0 0
1 0
0 0
0 1

Sample Output #1

1

Sample Input #2

3 3
0 0 0
0 1 0
1 0 1
0 1 0
1 0 1
0 1 0

Sample Output #2

4

Sample Input #3

3 4
0 0 0 0
1 1 0 0
0 0 0 0
1 1 1 0
0 1 0 0
0 0 0 0

Sample Output #3

3

Notes/Hints

Scoring

This problem has partial scoring.

• If you correctly solve all test cases where $N, M \leq 10$, you will be awarded $ 40 $ points.
• If you correctly solve all test cases, you will be awarded an additional $ 50 $ points.

Sample Explanation 1

Conversion is possible with a cost of 1 by swapping the squares in the lower row.

Sample Explanation 2

Conversion is possible with a cost of 4 by converting white to black once and swapping squares three times.

Sample Explanation 3

Conversion is possible with a cost of 3 by converting white to black twice and swapping squares once.

见题面 Input 部分

见题面 Output 部分