|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|1 초||512 MB||489||121||79||24.611%|
A company named ICPC (Interstellar Cosmology Progress Corporation) is working on a new telescope. It receives optical signals with an m × l grid of sensors. Each sensor detects the color and the intensity of light it receives. Then it filters noises and multiplies the intensity of light by some constant. All the lights sensors received are then merged on a rectangular film. ICPC believes that this telescope can easily beat current optical or radar telescopes because traditional noises are filtered.
However, an engineer found a critical flaw in design. The film can withstand the light with intensity up to W. If it is exposed to the light with intensity greater than W, the telescope may break down.
Consider what will happen in practice.
Consider the following example. The path is a 3 × 5 grid, the telescope is a 3 × 3 grid, and W = 20. Each T(i, j) is written on the left upper side of the grid and each P(i, j) is written on the lower right side of the grid. At position 1, the intensity of light is 1 × 1 + 4 × 1 + 11 × 1 = 16 < W. At position 2, it is 3 × 1 + 3 × 1 + 3 × 1 = 9 < W. You can see that it is smaller than W at position 3 too.
Figure L.1: An example of a telescope moving the path from left to right. (left) The telescope is at position 1 of the path. (right) Now the telescope moved to position 2.
Now you want to know how many times the telescope receives light with intensity greater than W, given the information on the sky and the telescope.
Your program is to read from standard input. The input starts with a line containing three integers, n (l ≤ n ≤ 10,000), l (2 ≤ l ≤ 3,000), m (2 ≤ m ≤ 100), and W (0 ≤ W ≤ 104 lm), where n is the number of columns in the path, l is the number of columns in the telescope, m is that of rows, and W is the threshold defined above. In the following m lines, information on each row of the path is given line by line. That is, T(i, j) is the jth number of line i + 1. Also, 0 ≤ T(i, j) ≤ 100. In the following m lines, information on each row of the sensors is given line by line. That is, P(i, j) is the jth number of line i + m + 1.
Your program is to write to standard output. Print exactly one line for the input. The line should contain the number of times when the intensity of light on the film is greater than W.
4 2 2 40 1 2 3 4 1 0 0 0 10 10 10 10
5 3 2 20 1 3 5 7 9 2 4 3 5 2 1 0 0 0 1 0