Stain

Interview

Time limit1sMemory limit1024 MB

Summary

Given a stain grid and a sticker grid, find the fewest stain cells left uncovered after rotating the sticker by 90-degree steps and shifting it anywhere.

Level: Easy3 of 10
Topics: Brute force, Matrix, Implementation
Solved: No attempts yet

Problem

Mirko spilled cocoa on his notebook, and a stain appeared in the middle of the front cover. Mirko will cover the stain with a sticker. To make things harder, both the stain and the sticker have irregular shapes, so Mirko may not be able to cover the whole stain.

The stain is described as a set of cells marked with # inside an imaginary N x N table that represents the middle of the cover. The sticker is described the same way, as a set of # cells inside an imaginary table of the same size. The examples below make this easier to follow.

Mirko can:

rotate the sticker by multiples of 90 degrees, without flipping it;
move the sticker in any direction to cover the stain as well as possible.

Option 1 means Mirko can place the sticker in four different orientations relative to the cover. Option 2 means the sticker may extend beyond the table that describes the stain.

Help Mirko write a program that answers this question: what is the minimum number of parts of the stain that remain visible under the sticker after covering? If the stain can be covered completely, the answer is zero.

The figure shows the third example. The stain is on the left and the sticker is in the middle. The sticker is rotated 90 degrees clockwise and then moved so that it covers everything except one part of the stain (the upper right one), as shown on the right.

Input

The first line contains the number N (1 $\le$ N $\le$ 10), the size of the imaginary table from the statement.

The next N lines each contain N characters without spaces, describing the stain. The character # marks a stain cell and . marks an empty cell.

An empty line follows, then N more lines of N characters each, describing the sticker in the same way.

The cells of the stain are connected, so the stain does not consist of separate pieces. The same holds for the sticker.

Output

Print one line containing the answer to the question in the statement.

Hint

In the first test case, the stain and the rotated sticker are exactly the same, so they overlap perfectly.

In the second test case, no matter how the sticker is placed, at least one part of the stain stays uncovered.

The third test case is the one shown in the figure in the statement.

Examples3

Example 1
Input
```
3
.#.
##.
...

##.
#..
...
```
Expected output
```
0
```

Example 2

Input

4
...#
...#
...#
..##

#.##
###.
#.##
##.#

Expected output

Example 3

Input

4
#.##
###.
##..
....

##..
.##.
####
..#.

Expected output