D - Inspection Schedule Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君は、全長 T km の高速道路の管理を担当しています。安全性を保つため、道路上にいくつかの点検区間を設置する必要があります。

高速道路の起点を地点 0 km、終点を地点 T km とします。

点検区間は、整数 s（0 \leq s かつ s + K \leq T）を選び、開区間 (s, s+K) として設置します。すなわち、地点 s km から地点 (s+K) km までの長さ K km の区間です。点検区間は 0 個以上いくつでも設置でき、異なる点検区間同士が重なっても構いません。

道路上には N 個のイベント会場があり、i 番目のイベント会場は開区間 (L_i, R_i)（地点 L_i km から地点 R_i km まで）を使用しています。ある点検区間 (s, s+K) がイベント会場 (L_i, R_i) と重なるとは、これら二つの開区間の共通部分が空でないことを指します。一つのイベント会場が複数の点検区間と重なっていても、影響を受けるイベント会場としては 1 個と数えます。

安全基準を満たすため、点検区間の配置は以下の間隔制約を満たさなければなりません。設置した点検区間の個数を p（p \geq 0）とし、それらの開始地点を昇順に s_1 \leq s_2 \leq \cdots \leq s_p とします。このとき、以下のすべてが成り立つ必要があります。

p = 0 の場合：

  • T \leq M

p \geq 1 の場合：

  • s_1 \leq M
  • s_{j+1} - (s_j + K) \leq M（1 \leq j \leq p-1）
  • T - (s_p + K) \leq M

1 番目の条件は、起点 0 km から最初の点検区間の開始地点までが M km 以下であること、2 番目の条件は、j 番目の点検区間の終了地点 s_j + K から j+1 番目の点検区間の開始地点 s_{j+1} までが M km 以下であること、3 番目の条件は、最後の点検区間の終了地点 s_p + K から終点 T km までが M km 以下であることを意味します。なお、2 番目の条件において点検区間同士が重なる場合は左辺が負になり、条件は自動的に満たされます。

直感的には、道路上のどの地点をとっても、そこから M km 以内にいずれかの点検区間が存在するように配置する必要がある、ということです。制約より M \geq K が保証されるため、例えば道路全体を隙間なく点検区間で覆うことが可能であり、間隔制約を満たす配置は常に存在します。

高橋君は、間隔制約を満たしながら点検区間を配置し、いずれかの点検区間と重なるイベント会場の数を最小化したいと考えています。その最小値を求めてください。

制約

  • 1 \leq T \leq 1000
  • 0 \leq N \leq 12
  • 1 \leq K \leq M \leq T
  • 0 \leq L_i < R_i \leq T（1 \leq i \leq N）
  • 入力はすべて整数

入力

T N K M
L_1 R_1
L_2 R_2
\vdots
L_N R_N
  • 1 行目には、高速道路の全長を表す T、イベント会場の数を表す N、点検区間の長さを表す K、間隔制約における距離の上限を表す M が、スペース区切りで与えられる。
  • 2 行目から N+1 行目では、各イベント会場の区間を表す L_i と R_i が、スペース区切りで与えられる。
  • 1+i 行目には、i 番目のイベント会場の開始地点 L_i と終了地点 R_i が与えられる。

出力

間隔制約を満たす点検区間の配置において、いずれかの点検区間と重なるイベント会場の数の最小値を 1 行で出力せよ。

入力例 1

10 3 2 3
1 2
4 6
8 9

出力例 1

0

入力例 2

6 2 2 6
1 3
4 6

出力例 2

0

入力例 3

50 8 5 9
0 4
6 10
12 18
19 23
25 31
33 37
39 45
46 50

出力例 3

4

入力例 4

200 12 17 30
0 12
15 28
31 45
48 63
70 82
85 101
105 119
123 140
142 158
160 176
178 190
191 200

出力例 4

5

入力例 5

1 0 1 1

出力例 5

0

Score : 400 pts

Problem Statement

Takahashi is in charge of managing a highway with a total length of T km. To maintain safety, he needs to set up several inspection intervals along the highway.

Let the starting point of the highway be 0 km and the ending point be T km.

An inspection interval is set up by choosing an integer s (0 \leq s and s + K \leq T) as an open interval (s, s+K). That is, it is an interval of length K km from point s km to point (s+K) km. You can set up any number of inspection intervals (including 0), and different inspection intervals may overlap.

There are N event venues along the highway, where the i-th event venue uses the open interval (L_i, R_i) (from point L_i km to point R_i km). We say that an inspection interval (s, s+K) overlaps with an event venue (L_i, R_i) if the intersection of these two open intervals is non-empty. Even if a single event venue overlaps with multiple inspection intervals, it is counted as 1 affected event venue.

To meet safety standards, the placement of the inspection intervals must satisfy the following interval constraints. Let p (p \geq 0) be the number of inspection intervals set up, and let their starting points in non-decreasing order be s_1 \leq s_2 \leq \cdots \leq s_p. Then, all of the following must hold:

If p = 0:

  • T \leq M

If p \geq 1:

  • s_1 \leq M
  • s_{j+1} - (s_j + K) \leq M (1 \leq j \leq p-1)
  • T - (s_p + K) \leq M

The first condition means that the distance from the starting point 0 km to the starting point of the first inspection interval is at most M km. The second condition means that the distance from the ending point of the j-th inspection interval s_j + K to the starting point of the (j+1)-th inspection interval s_{j+1} is at most M km. The third condition means that the distance from the ending point of the last inspection interval s_p + K to the ending point T km is at most M km. Note that if the inspection intervals overlap in the second condition, the left-hand side becomes negative, and the condition is automatically satisfied.

Intuitively, this means that for any point on the highway, there must be some inspection interval within M km of it. Since the constraints guarantee M \geq K, it is always possible to, for example, cover the entire highway with inspection intervals without gaps, so a placement satisfying the interval constraints always exists.

Takahashi wants to place the inspection intervals to satisfy the interval constraints while minimizing the number of event venues that overlap with at least one inspection interval. Find this minimum value.

Constraints

  • 1 \leq T \leq 1000
  • 0 \leq N \leq 12
  • 1 \leq K \leq M \leq T
  • 0 \leq L_i < R_i \leq T (1 \leq i \leq N)
  • All input values are integers.

Input

T N K M
L_1 R_1
L_2 R_2
\vdots
L_N R_N
  • The first line contains four space-separated integers: T, the total length of the highway; N, the number of event venues; K, the length of each inspection interval; and M, the upper limit of the distance in the interval constraints.
  • The next N lines describe the intervals of each event venue.
  • The (1+i)-th line contains two space-separated integers, L_i and R_i, representing the starting and ending points of the i-th event venue.

Output

Print the minimum number of event venues that overlap with at least one inspection interval in a placement that satisfies the interval constraints, in a single line.

Sample Input 1

10 3 2 3
1 2
4 6
8 9

Sample Output 1

0

Sample Input 2

6 2 2 6
1 3
4 6

Sample Output 2

0

Sample Input 3

50 8 5 9
0 4
6 10
12 18
19 23
25 31
33 37
39 45
46 50

Sample Output 3

4

Sample Input 4

200 12 17 30
0 12
15 28
31 45
48 63
70 82
85 101
105 119
123 140
142 158
160 176
178 190
191 200

Sample Output 4

5

Sample Input 5

1 0 1 1

Sample Output 5

0