C - イベント巡り (Event Hopping) 解説 /

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

配点： 100 点

問題文

IOI 国には 2 個の町があり，それぞれ 1, 2 と番号がついている．

これらの町では合計 N 個のイベントが行われる．これらのイベントには 1 から N までの番号がついている．イベント i (1 \leqq i \leqq N) は町 P_i で開催され，開催時刻は時刻 S_i + 0.1 から時刻 S_i + 0.9 までである．ここで S_i は整数である．JOI 君がイベント i に参加するためには，時刻 S_i + 0.1 から時刻 S_i + 0.9 までの間，ずっと町 P_i にいる必要がある．

JOI 君はイベント巡りを行うことにした．イベント巡りではいくつかのイベントに参加し，必要ならば町と町の間を移動することもできる．JOI 君は時刻 0 からイベント巡りを開始する．このとき，好きな町から始めることができる．

JOI 君は町 1 と町 2 の間を双方向に移動することができる．2 つの町の間を移動するのにかかる時間は，JOI 君がその移動を開始する時刻までに参加したイベントの数を j として，D + K \times j となる．

イベントと町の間の移動に関する情報が与えられるので，JOI 君が参加できるイベントの数の最大値を求めるプログラムを作成せよ．

制約

  • 1 \leqq N \leqq 200\,000．
  • 1 \leqq D \leqq 10^{12}．
  • 0 \leqq K \leqq 10^{12}．
  • 1 \leqq P_i \leqq 2 (1 \leqq i \leqq N)．
  • 1 \leqq S_i \leqq 10^{12} (1 \leqq i \leqq N)．
  • S_i \neq S_j (1 \leqq i < j \leqq N)．
  • 入力される値はすべて整数である．

小課題

  1. (8 点) K = 0，N \leqq 20．
  2. (11 点) K = 0，N \leqq 4\,000．
  3. (24 点) K = 0．
  4. (12 点) N \leqq 160．
  5. (23 点) N \leqq 4\,000．
  6. (22 点) 追加の制約はない．

入力

入力は以下の形式で標準入力から与えられる．

N D K
P_1 S_1
P_2 S_2
\vdots
P_N S_N

出力

標準出力に，JOI 君が参加することのできるイベントの数の最大値を 1 行で出力せよ．

入力例 1

5 3 0
1 1
1 2
1 10
2 5
2 6

出力例 1

4

例えば，以下のように行動することで，JOI 君は 4 個のイベントに参加することができる．

  1. 時刻 0 において JOI 君は町 1 にいる．
  2. 時刻 1.1 から時刻 1.9 まで町 1 でイベント 1 に参加する．
  3. 時刻 2.1 から時刻 2.9 まで町 1 でイベント 2 に参加する．
  4. 時刻 3 から時刻 6 まで時間 3 (= D + K \times 2) をかけて町 1 から町 2 に移動する．
  5. 時刻 6.1 から時刻 6.9 まで町 2 でイベント 5 に参加する．
  6. 時刻 7 から時刻 10 まで時間 3 (= D + K \times 3) をかけて町 2 から町 1 に移動する．
  7. 時刻 10.1 から時刻 10.9 まで町 1 でイベント 3 に参加する．

どのように行動しても 5 個以上のイベントに参加することはできないため，4 を出力する．

この入力例はすべての小課題の制約を満たす．

入力例 2

7 2 3
2 2
1 8
1 10
1 11
2 23
2 24
2 25

出力例 2

6

例えば，以下のように行動することで，JOI 君は 6 個のイベントに参加することができる．

  1. 時刻 0 において JOI 君は町 2 にいる．
  2. 時刻 2.1 から時刻 2.9 まで町 2 でイベント 1 に参加する．
  3. 時刻 3 から時刻 8 まで時間 5 (= D + K \times 1) をかけて町 2 から町 1 に移動する．
  4. 時刻 8.1 から時刻 8.9 まで町 1 でイベント 2 に参加する．
  5. 時刻 11.1 から時刻 11.9 まで町 1 でイベント 4 に参加する．
  6. 時刻 12 から時刻 23 まで時間 11 (= D + K \times 3) をかけて町 1 から町 2 に移動する．
  7. 時刻 23.1 から時刻 23.9 まで町 2 でイベント 5 に参加する．
  8. 時刻 24.1 から時刻 24.9 まで町 2 でイベント 6 に参加する．
  9. 時刻 25.1 から時刻 25.9 まで町 2 でイベント 7 に参加する．

どのように行動しても 7 個以上のイベントに参加することはできないため，6 を出力する．

この入力例は小課題 4, 5, 6 の制約を満たす．

入力例 3

12 153 0
1 155
2 861
1 646
1 218
2 450
2 56
1 932
2 295
2 863
1 612
2 38
2 768

出力例 3

8

この入力例はすべての小課題の制約を満たす．

入力例 4

15 89 104
1 4379
1 738
1 4862
1 4236
2 1416
1 9905
1 4775
2 4574
2 439
1 3956
1 955
2 8862
2 801
2 2299
2 575

出力例 4

11

この入力例は小課題 4, 5, 6 の制約を満たす．