30508번 - 고인물이싫어

문제

비 오는 날 세종이는 부모님의 심부름으로 물을 사러 갔다. 횡단보도 앞에서 신호를 기다리던 세종이는 횡단보도가 평평하지 않아 물이 고인 것을 보았다. 횡단보도는 $N\times M$ 크기의 직사각형 격자 모양이며, 세종이가 서 있는 쪽 맨 앞의 맨 왼쪽 칸을 1ドル$행 1ドル$열, 맨 오른쪽 칸을 1ドル$행 $M$열로 부른다.

횡단보도 중 $K$개의 칸에는 하수구가 있다. 모든 칸은 상하좌우로 인접한 칸 중 높이가 자신보다 낮거나 같은 칸에 하수구나 물이 빠진 칸이 있으면 물이 빠진다. 하수구가 없는 칸 중 물이 빠지지 않은 칸을 물이 고인 칸이라고 한다. A+B를 풀고 받은 새 신발을 더럽히고 싶지 않았던 세종이는 물이 고인 칸을 밟지 않고 횡단보도를 건너려 한다. 세종이의 새 신발은 횡단보도의 연속된 $h$개의 행과 $w$개의 열을 덮는 크기의 직사각형 모양이다. 세종이는 횡단보도를 건널 때 항상 신발이 횡단보도의 격자 칸에 꼭 맞게 들어가게 발을 딛으며, 발의 방향을 돌리지 않는다.

횡단보도의 각 칸의 높이가 주어졌을 때, 세종이가 횡단보도에 신발을 더럽히지 않고 한쪽 발을 딛는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 횡단보도의 크기를 나타내는 두 정수 $N,M$이 공백으로 구분되어 주어진다. $(1\le N,M\le 1,円 000)$

둘째 줄에 세종이의 신발의 길이와 너비를 나타내는 두 정수 $h,w$가 공백으로 구분되어 주어진다. $(1\le h\le N;$ 1ドル\le w\le M)$

그다음 $N$개의 줄에 걸쳐, $i+2$번째 줄에 $M$개의 정수 $H[i][1] ,H[i][2] ,\cdots ,H[i][M]$이 공백으로 구분되어 주어진다. 이때 $H[i][j]$는 횡단보도의 $i$행 $j$열에 해당하는 칸의 높이를 의미한다. $(1 \le H[i][j] \le 100)$

$N+3$번째 줄에 하수구의 수를 나타내는 정수 $K$가 주어진다. $(1\le K\le N\times M)$

그다음 $K$개의 줄에 걸쳐 하수구의 위치를 나타내는 두 정수 $r,c$가 공백으로 구분되어 주어진다. 이는 횡단보도의 $r$행 $c$열에 하수구가 있음을 의미한다. 입력으로 주어지는 위치는 중복되지 않는다. $(1\le r\le N;$ 1ドル\le c\le M)$

출력

첫째 줄에 세종이가 횡단보도에 한쪽 발을 딛는 방법의 수를 출력한다.

제한

힌트