Madness

Time limit2sMemory limit1024 MB

Summary

Given apartment ids and lit windows on a grid, find the fewest apartments to change so a target lit/dark pattern appears as a sub-rectangle.

Level: Medium7 of 10
Topics: Matrix, String matching, Hash map
Solved: No attempts yet

Problem

Seryozha wanted to do something crazy. For example, make a nice word appear on the wall of the building opposite.

He drew on graph paper a map of an $a \times b$ grid showing which windows should be lit and which should be dark. Seryozha counts a word as written on the building if, inside some rectangle, the pattern of lit and dark windows matches his drawing. The state of the other windows does not matter.

To switch a window on or off, Seryozha must agree with the owner of the apartment. After that, he can switch the lights in any windows of that apartment in any way he likes.

He has a floor plan and knows which apartment each window belongs to. Each apartment consists of several adjacent windows on the same floor.

What is the minimum number of owners Seryozha must agree with?

Input

The first line contains integers $n$ and $m$ ( $1 \le n,m \le 50$ ). The next $n$ lines each contain $m$ integers. The $j$ -th number in line $i+1$ is the apartment number of the $j$ -th window from the left on floor $n-i+2$ of the building. Apartment numbers are positive integers not exceeding 5000.

The next $n$ lines each contain a string of $m$ characters. '#' means the light is on, and '.' means it is off.

The next line contains integers $a$ and $b$ ( $1 \le a \le n$ , $1 \le b \le m$ ). The next $a$ lines each contain a string of $b$ characters. '#' means that window must be lit in the word, and '.' means it must be dark.

Output

Print one integer: the minimum number of apartments whose owners Seryozha must agree with.

Examples1

Example 1

Input

5 26
33 33 33 33 34 34 35 35 35 35 36 36 36 37 37 37 37 38 38 38 39 39 39 40 40 40
25 25 25 25 26 26 27 27 27 27 28 28 28 29 29 29 29 30 30 30 31 31 31 32 32 32
17 17 17 17 18 18 19 19 19 19 20 20 20 21 21 21 21 22 22 22 23 23 23 24 24 24
9  9  9  9 10 10 11 11 11 11 12 12 12 13 13 13 13 14 14 14 15 15 15 16 16 16
1  1  1  1  2  2  3  3  3  3  4  4  4  5  5  5  5  6  6  6  7  7  7  8  8  8
#.#....###..#.#####..#....
.##.####..#.#.##.#..##.###
....####..#....#....#.#..#
..#...#.##...#.#..#####...
...#....#.###.#.#......##.
5 25
#.#.#.#...#.###...#..###.
.###..#..##.#..#..#.#.#.#
..#...#.#.#.###..#.#.###.
.###..##..#.#...#####.#..
#.#.#.#...#.#...#...#.#..

Expected output