만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

광기

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

요약
건물 창문마다 아파트 번호와 켜진 상태가 주어질 때, 목표 무늬가 직사각형 안에 나타나도록 동의를 받을 아파트 수의 최솟값을 구합니다.
난이도

보통10점 중 7점

유형
행렬, 문자열 매칭, 해시맵
정답자
아직 제출이 없습니다

문제

세레자는 무언가 미친 짓을 하고 싶어졌다. 예를 들어 맞은편 건물의 벽에 좋은 단어가 떠오르게 만드는 것이다.

그는 모눈종이에 a×ba \times b 크기의 지도를 그렸다. 지도에는 어느 창문의 불을 켜고 어느 창문을 끌지가 표시되어 있다. 어떤 직사각형 안에서 켜진 창문과 꺼진 창문의 배치가 이 그림과 일치하면, 세레자는 건물에 단어가 쓰였다고 본다. 나머지 창문의 상태는 상관없다.

창문의 불을 켜거나 끄려면 세레자가 그 집의 주인과 합의해야 한다. 합의하면 세레자는 그 집의 어떤 창문이든 원하는 대로 불을 켜고 끌 수 있다.

그는 건물 평면도를 가지고 있어서 각 창문이 어느 집에 속하는지 알고 있다. 각 집은 같은 층에 있는 연속된 여러 창문으로 이루어져 있다.

세레자가 합의해야 하는 집주인의 최소 수는 얼마인가?

입력

첫 줄에 정수 nn과 mm (1≤n,m≤501 \le n,m \le 50)이 주어진다. 이어서 nn개의 줄에 각각 mm개의 정수가 주어진다. i+1i+1번째 줄의 jj번째 수는 건물의 n−i+2n-i+2층에서 왼쪽부터 jj번째 창문이 속한 집의 번호이다. 집 번호는 5000 이하의 양의 정수이다.

이어서 nn개의 줄에 각각 mm개의 문자로 된 문자열이 주어진다. '#'은 불이 켜져 있음, '.'은 꺼져 있음을 뜻한다.

다음 줄에 정수 aa와 bb (1≤a≤n1 \le a \le n, 1≤b≤m1 \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