망원경

ICPC(Interstellar Cosmology Progress Corporation)는 새 망원경을 만들고 있다. 이 망원경은 $m \times l$ 크기의 센서 격자로 광학 신호를 받는다. 센서 하나하나가 들어온 빛의 색과 세기를 측정하고, 장치는 잡음을 걸러낸 뒤 세기에 일정한 상수를 곱한다. 센서가 모은 빛은 모두 하나의 직사각형 필름 위에서 합쳐진다. 잡음이 제거되므로 ICPC는 이 망원경이 지금의 광학 망원경이나 전파 망원경을 앞선다고 본다.

그런데 한 기술자가 설계의 결함을 찾아냈다. 필름이 견디는 빛의 세기는 $W$까지다. 세기가 $W$를 넘는 빛에 노출되면 망원경이 고장날 수 있다.

실제 동작은 이렇다.

1. 망원경은 하늘의 한 지점을 향하고 있다가 시간이 지나면 오른쪽으로 움직인다. 즉 하늘을 왼쪽에서 오른쪽으로 훑는다.
2. 망원경은 $m \times l$ 격자다. 망원경의 $(i, j)$ 칸에 있는 센서($1 \le i \le m$, $1 \le j \le l$)는 받은 빛을 $P(i, j)$배로 증폭한다. 여기서 $0 \le P(i, j) \le 100$이다.
3. 망원경이 훑는 하늘의 경로는 $m \times n$ 격자다. $T(i, j)$는 경로의 $(i, j)$ 칸에 있는 빛의 세기다($1 \le i \le m$, $1 \le j \le n$).
4. 처음에 망원경은 경로의 1번 위치에 있다. 즉 망원경의 $(i, j)$ 칸 센서($1 \le i \le m$, $1 \le j \le l$)가 경로의 $(i, j)$ 칸과 맞춰진다. 덮인 경로의 칸 하나는 망원경의 칸 정확히 하나가 덮는다.
5. $k$분이 지나면 망원경은 $k + 1$번 위치에 있다. 망원경의 $(i, j)$ 칸 센서가 경로의 $(i, j + k)$ 칸과 맞춰진다.
6. $k + 1$번 위치에서 빛의 세기는 $W_k = \sum_{i=1}^{m} \sum_{j=1}^{l} T(i, j + k) \, P(i, j)$이다. $W_k > W$이면 망원경이 고장날 수 있다. 망원경의 마지막 위치는 $n - l + 1$번이다.

아래 예를 보자. 경로는 $3 \times 5$ 격자, 망원경은 $3 \times 3$ 격자, $W = 20$이다. 각 칸의 왼쪽 위에 $T(i, j)$를, 오른쪽 아래에 $P(i, j)$를 적었다. 1번 위치에서 빛의 세기는 $1 \times 1 + 4 \times 1 + 11 \times 1 = 16 < W$이다. 2번 위치에서는 $3 \times 1 + 3 \times 1 + 3 \times 1 = 9 < W$이다. 3번 위치에서도 $W$보다 작다.

그림 L.1: 망원경이 경로를 왼쪽에서 오른쪽으로 지나간다. 왼쪽은 망원경이 1번 위치에 있는 모습이고, 오른쪽은 2번 위치로 움직인 모습이다.

하늘과 망원경의 정보가 주어질 때, 망원경이 세기가 $W$보다 큰 빛을 받는 횟수를 구하여라.

첫째 줄에 네 정수 $n$, $l$, $m$, $W$가 주어진다($l \le n \le 10{,}000$, $2 \le l \le 3{,}000$, $2 \le m \le 100$, $0 \le W \le 10^4 \times l \times m$). $n$은 경로의 열 개수, $l$은 망원경의 열 개수, $m$은 둘의 행 개수, $W$는 위에서 정한 한계다.

다음 $m$개 줄에는 경로의 각 행이 한 줄씩 주어진다. $i + 1$번째 줄에는 $T(i, 1), T(i, 2), \ldots, T(i, n)$이 공백으로 구분되어 주어지며, $0 \le T(i, j) \le 100$이다.

그다음 $m$개 줄에는 센서의 각 행이 한 줄씩 주어진다. $i + m + 1$번째 줄에는 $P(i, 1), P(i, 2), \ldots, P(i, l)$이 공백으로 구분되어 주어지며, $0 \le P(i, j) \le 100$이다.

필름에 닿는 빛의 세기가 $W$보다 큰 위치의 개수를 한 줄에 출력한다. 부등호는 엄격하므로 세기가 $W$와 같은 위치는 세지 않는다.