Безумие

시간 제한2초메모리 제한1024 MB

요약
창문 격자 안에서 패턴을 놓을 위치를 골라, 상태를 바꿔야 하는 창문이 속한 아파트 수가 최소가 되게 한다.
난이도

보통10점 중 6점

유형
완전 탐색, 해시맵, 구현
정답자
아직 제출이 없습니다

문제

Сереже очень захотелось сделать что-нибудь безумное. Например, сделать так, что бы на стене дома напротив высветилось какое-нибудь хорошее слово.

Он нарисовал на клетчатом листочке размером a×ba \times b карту того, в каких окна должен гореть свет, а в каких нет. Сережа будет считать, что на доме написано слово, если внутри некоторого прямоугольника картина включенных и выключенных окон будет совпадать с этим рисунком, при этом не важно горит свет или нет в остальных окнах.

Для этого ему необходимо в некоторых окнах свет включить, а в некоторых выключить. Однако, чтобы включить или выключить свет в окне, Сереже надо договориться с хозяином квартиры. После этого он сможет произвольным образом включать и выключать свет в любых окнах этой квартиры.

У него есть план дома, и он знает какой квартире принадлежит какое окно. Ему удалось выяснить, что каждой квартире принадлежит несколько соседних окон на одном этаже.

С каким минимальным количеством хозяев надо договориться?

입력

В первой строке входного файла два целых числа nn и mm (1≤n,m≤501 \le n,m \le 50).

Далее следуют nn строк по mm чисел в каждой --- какой квартире принадлежит соответствующее окно. В i+1i + 1-ой строке входного файла на jj-ой позиции стоит номер квартиры, которой принадлежит jj-ое слева окно на n−i+2n - i + 2-ом этаже дома. Номера квартир --- целые положительные числа, не превосходящие 5000.

Потом следуют nn строк по mm символов в каждой --- <<#>> означает, что свет в соответствующем окне горит, а <<.>>, что нет.

В следующей строке находятся два целых числа aa и bb (1≤a≤n,1≤b≤m1 \le a \le n, 1 \le b \le m). Затем следуют aa строк по bb символов в каждой --- <<#>> означает, что соответствующее окно должно светиться в Сережином слове, а <<.>>, что не должно.

출력

В выходной файл выведите единственное число --- минимальное число квартир, с хозяевами которых должен договориться Сережа.

예제1

  1. 예제 1

    입력
    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
#.#.#.#...#.###...#..###.
.###..#..##.#..#..#.#.#.#
..#...#.#.#.###..#.#.###.
.###..##..#.#...#####.#..
#.#.#.#...#.#...#...#.#..
    예상 출력
    35