E - 気温変動の監視 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 466 点

問題文

高橋君は気象データの分析を担当しています。彼の仕事は、複数の観測地点の気温データを調べ、気温変動が激しい地点を報告することです。

観測地点は N 箇所あり、それぞれの観測地点 i （ 1 \leq i \leq N ）では、過去 M 日間の日平均気温 S_{i,1}, S_{i,2}, \ldots, S_{i,M} が記録されています。

高橋君は、各観測地点について「気温変動スコア」を算出することにしました。観測地点 i の気温変動スコアは、以下のように定義されます：

  • 過去 M 日間の気温データの中から、連続する K 日間を選ぶすべての方法を考える。それぞれの連続 K 日間について、その区間内の気温の最大値と最小値の差を求める。
  • それらの差のうち、最大のものを観測地点 i の気温変動スコアとする。

高橋君は、気温変動スコアが閾値 T 以上である観測地点の数を報告する必要があります。

気温変動スコアが T 以上である観測地点の数を求めてください。

制約

  • 1 \leq N \leq 500
  • 1 \leq K \leq M \leq 10^5
  • N \times M \leq 2 \times 10^6
  • -10^9 \leq S_{i,j} \leq 10^9
  • 0 \leq T \leq 2 \times 10^9
  • 入力はすべて整数である。

入力

N M K T
S_{1,1} S_{1,2} \ldots S_{1,M}
S_{2,1} S_{2,2} \ldots S_{2,M}
\vdots
S_{N,1} S_{N,2} \ldots S_{N,M}
  • 1 行目には、観測地点の数を表す N 、日数を表す M 、連続日数を表す K 、閾値を表す T が、スペース区切りで与えられる。
  • 2 行目から N + 1 行目には、各観測地点の気温データが与えられる。
  • 1 + i 行目では、観測地点 i の M 日間の気温 S_{i,1}, S_{i,2}, \ldots, S_{i,M} がスペース区切りで与えられる。

出力

気温変動スコアが T 以上である観測地点の数を 1 行で出力せよ。

入力例 1

3 5 3 5
1 3 4 8 2
10 11 12 13 14
0 -5 -1 -2 1

出力例 1

2

入力例 2

2 4 2 10
1 2 3 4
-5 -4 -6 -5

出力例 2

0

入力例 3

5 10 4 12
1 2 3 4 5 6 7 8 9 10
10 -5 8 7 6 5 4 3 2 1
-10 -8 -6 -4 -2 0 2 4 6 8
100 90 80 70 60 50 40 30 20 10
5 5 20 5 5 5 -10 5 5 5

出力例 3

3

入力例 4

8 15 5 20
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
30 25 20 15 10 5 0 -5 -10 -15 -20 -25 -30 -35 -40
-5 -5 -5 -5 -5 -5 -5 -5 -5 -5 -5 -5 -5 -5 -5
100 80 100 80 100 80 100 80 100 80 100 80 100 80 100
1 50 2 49 3 48 4 47 5 46 6 45 7 44 8
-100 -90 -80 -70 -60 -50 -40 -30 -20 -10 0 10 20 30 40
7 8 6 9 5 10 4 11 3 12 2 13 1 14 0
1000000000 999999990 999999980 999999970 999999960 -1000000000 -999999990 -999999980 -999999970 -999999960 0 10 20 30 40

出力例 4

5

入力例 5

1 1 1 0
-1000000000

出力例 5

1

Score : 466 pts

Problem Statement

Takahashi is in charge of analyzing weather data. His job is to examine temperature data from multiple observation stations and report stations with severe temperature fluctuations.

There are N observation stations. For each observation station i (1 \leq i \leq N), the daily average temperatures for the past M days, S_{i,1}, S_{i,2}, \ldots, S_{i,M}, are recorded.

Takahashi has decided to calculate a "temperature fluctuation score" for each observation station. The temperature fluctuation score for station i is defined as follows:

  • Consider all possible ways to choose K consecutive days from the past M days of temperature data. For each interval of K consecutive days, find the difference between the maximum and minimum temperatures within that interval.
  • The maximum of these differences is defined as the temperature fluctuation score of station i.

Takahashi needs to report the number of observation stations whose temperature fluctuation score is at least the threshold T.

Find the number of observation stations with a temperature fluctuation score of T or higher.

Constraints

  • 1 \leq N \leq 500
  • 1 \leq K \leq M \leq 10^5
  • N \times M \leq 2 \times 10^6
  • -10^9 \leq S_{i,j} \leq 10^9
  • 0 \leq T \leq 2 \times 10^9
  • All input values are integers.

Input

N M K T
S_{1,1} S_{1,2} \ldots S_{1,M}
S_{2,1} S_{2,2} \ldots S_{2,M}
\vdots
S_{N,1} S_{N,2} \ldots S_{N,M}
  • The first line contains N (the number of observation stations), M (the number of days), K (the number of consecutive days), and T (the threshold), separated by spaces.
  • The 2-nd to (N + 1)-th lines contain the temperature data for each observation station.
  • The (1 + i)-th line contains the temperatures of station i for M days, S_{i,1}, S_{i,2}, \ldots, S_{i,M}, separated by spaces.

Output

Print the number of observation stations with a temperature fluctuation score of at least T in a single line.

Sample Input 1

3 5 3 5
1 3 4 8 2
10 11 12 13 14
0 -5 -1 -2 1

Sample Output 1

2

Sample Input 2

2 4 2 10
1 2 3 4
-5 -4 -6 -5

Sample Output 2

0

Sample Input 3

5 10 4 12
1 2 3 4 5 6 7 8 9 10
10 -5 8 7 6 5 4 3 2 1
-10 -8 -6 -4 -2 0 2 4 6 8
100 90 80 70 60 50 40 30 20 10
5 5 20 5 5 5 -10 5 5 5

Sample Output 3

3

Sample Input 4

8 15 5 20
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
30 25 20 15 10 5 0 -5 -10 -15 -20 -25 -30 -35 -40
-5 -5 -5 -5 -5 -5 -5 -5 -5 -5 -5 -5 -5 -5 -5
100 80 100 80 100 80 100 80 100 80 100 80 100 80 100
1 50 2 49 3 48 4 47 5 46 6 45 7 44 8
-100 -90 -80 -70 -60 -50 -40 -30 -20 -10 0 10 20 30 40
7 8 6 9 5 10 4 11 3 12 2 13 1 14 0
1000000000 999999990 999999980 999999970 999999960 -1000000000 -999999990 -999999980 -999999970 -999999960 0 10 20 30 40

Sample Output 4

5

Sample Input 5

1 1 1 0
-1000000000

Sample Output 5

1