레이팅 미적용IOI 国には 2 個の町があり,それぞれ 1, 2 と番号がついている.
これらの町では合計 N 個のイベントが行われる.これらのイベントには 1 から N までの番号がついている.イベント i ( \(1 \le i \le 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 × j となる.
イベントと町の間の移動に関する情報が与えられるので,JOI 君が参加できるイベントの数の最大値を求めるプログラムを作成せよ.
1 ≦ N ≦ 200 000 .
1 ≦ D ≦ 10 12 .
0 ≦ K ≦ 10 12 .
1 ≦ P i ≦ 2 ( \(1 \le i \le N\) ).
1 ≦ S i ≦ 10 12 ( \(1 \le i \le N\) ).
S i ≠ S j ( \(1 \le i < j \le N\) ).
入力される値はすべて整数である.
( 8 点) K = 0 , \(N \le 20\) .
( 11 点) K = 0 , N ≦ 4 000 .
( 24 点) K = 0 .
( 12 点) \(N \le 160\) .
( 23 点) N ≦ 4 000 .
( 22 点) 追加の制約はない.
入力は以下の形式で標準入力から与えられる.
N D K
P 1 S 1
P 2 S 2
:
P N S N
標準出力に,JOI 君が参加することのできるイベントの数の最大値を 1 行で出力せよ.
5 3 0
1 1
1 2
1 10
2 5
2 6
4
7 2 3
2 2
1 8
1 10
1 11
2 23
2 24
2 25
6
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
8
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
11