33900번 - 캠핑장 부지 평탄화

문제

(주)영일건설은 정적산 일대의 아름다운 경관을 널리 알리고자, 이 지역에 $R \times C$ 크기의 부지를 선정하여 캠핑장을 조성할 계획이다.

캠핑장을 짓기 위해서는, 지반을 고르게 다지는 기초 평탄화 작업이 필요하며, 이를 위해 사전에 정의된 작업 계획도를 활용한다.

작업 계획도는 $R \times C$ 크기의 격자판으로, 각 칸에는 해당 위치에서 얼마만큼 고도를 줄여야 하는지가 기록되어 있다. 즉, 작업 계획도는 캠핑장 부지를 평평하게 만들기 위한 설계도로, 모든 지점의 고도를 줄이는 방향으로만 작업이 이루어진다.

정적산 일대의 지형은 $N \times M$ 크기의 지도로 주어지며, 이는 각 지점의 해발 고도를 담은 격자 형태의 데이터다.

이 지도에서 작업 계획도의 크기와 같은 $R \times C$ 크기의 격자 영역을 선택하여, 작업 계획도와 정확히 겹치도록 한 후, 각 지점에 대해 지도에 적힌 고도에서 작업 계획도에 적힌 값을 빼보았을 때, 해당 격자 영역 내 모든 지점의 고도가 동일해진다면 해당 위치는 평탄화가 가능한 부지로 판단한다. 단, 작업 계획도는 회전하거나 변형할 수 없으며, 주어진 형태 그대로 적용해야 한다. 음수의 고도로도 평탄화가 가능함에 유의한다.

캠핑장 부지는 아직 확정되지 않았기 때문에, 먼저 평탄화가 가능한 후보 부지들을 지도에서 탐색해야 한다.

주어진 지도와 작업 계획도를 바탕으로, 평탄화가 가능한 $R \times C$ 크기의 부지가 총 몇 곳인지 확인해 보자.

입력

첫 번째 줄에 지도의 행의 개수와 열의 개수를 나타내는 두 정수 $N,ドル $M$ 그리고 작업 계획도의 행의 개수와 열의 개수를 나타내는 $R,ドル $C$가 공백으로 구분되어 주어진다. $(1 \leq N, M \leq 1,000円;$ 1ドル \leq R \leq \min(9, N);$ 1ドル \leq C \leq \min(9, M);$ 1ドル \leq R \times C \leq 9)$

두 번째 줄부터 $N$개의 줄에 걸쳐 지도의 고도 정보가 주어진다. 각 줄은 한 행에 해당하며, $M$개의 정수가 공백으로 구분되어 주어진다. 이 정수들은 해당 행의 첫 번째 열부터 $M$번째 열까지의 해발 고도를 의미하며, 1ドル$ 이상 9ドル$ 이하의 정수이다.

그다음 줄부터 $R$개의 줄에 걸쳐 작업 계획도 정보가 주어진다. 각 줄은 한 행에 해당하며, $C$개의 정수가 공백으로 구분되어 주어진다. 이 정수들은 해당 행의 첫 번째 열부터 $C$번째 열까지의 줄여야 하는 고도를 의미하며, 0ドル$ 이상 9ドル$ 이하의 정수이다.

출력

평탄화 가능한 후보지 최대 개수를 출력한다.

제한

힌트