광기
시간 제한2초메모리 제한1024 MB
건물 창문마다 아파트 번호와 켜진 상태가 주어질 때, 목표 무늬가 직사각형 안에 나타나도록 동의를 받을 아파트 수의 최솟값을 구합니다.
문제
세레자는 무언가 미친 짓을 하고 싶어졌다. 예를 들어 맞은편 건물의 벽에 좋은 단어가 떠오르게 만드는 것이다.
그는 모눈종이에 크기의 지도를 그렸다. 지도에는 어느 창문의 불을 켜고 어느 창문을 끌지가 표시되어 있다. 어떤 직사각형 안에서 켜진 창문과 꺼진 창문의 배치가 이 그림과 일치하면, 세레자는 건물에 단어가 쓰였다고 본다. 나머지 창문의 상태는 상관없다.
창문의 불을 켜거나 끄려면 세레자가 그 집의 주인과 합의해야 한다. 합의하면 세레자는 그 집의 어떤 창문이든 원하는 대로 불을 켜고 끌 수 있다.
그는 건물 평면도를 가지고 있어서 각 창문이 어느 집에 속하는지 알고 있다. 각 집은 같은 층에 있는 연속된 여러 창문으로 이루어져 있다.
세레자가 합의해야 하는 집주인의 최소 수는 얼마인가?
입력
첫 줄에 정수 과 ()이 주어진다. 이어서 개의 줄에 각각 개의 정수가 주어진다. 번째 줄의 번째 수는 건물의 층에서 왼쪽부터 번째 창문이 속한 집의 번호이다. 집 번호는 5000 이하의 양의 정수이다.
이어서 개의 줄에 각각 개의 문자로 된 문자열이 주어진다. '#'은 불이 켜져 있음, '.'은 꺼져 있음을 뜻한다.
다음 줄에 정수 와 (, )가 주어진다. 이어서 개의 줄에 각각 개의 문자로 된 문자열이 주어진다. '#'은 세레자의 단어에서 해당 창문이 켜져 있어야 함을, '.'은 꺼져 있어야 함을 뜻한다.
출력
합의해야 하는 집주인의 최소 수를 나타내는 정수 하나를 출력한다.