展覧会 2

JOI 美術館には，東西方向にまっすぐに伸びる廊下に N 枚の絵が飾られており，1 から N までの番号が付けられている．絵 i (1 ≦ i ≦ N) は廊下の西端から X_i メートルの位置に飾られており，その価値は V_i である．

この美術館では明日から「エゴイ展」が開催される予定であり，非常に多くの来客が見込まれている．「エゴイ展」では M 枚の絵を展示する予定である．

2 つの絵が近い位置に展示されていると見づらいので，以下の条件を満たすように N-M 枚の絵を取り外し，廊下に M 枚の絵だけを残すことにした．

• どの 2 つの絵についても，位置が D メートル以上離れているようにする．

展示されている M 枚の絵の価値の最小値を，「エゴイ展」の華やかさとする．あなたは，廊下に残す M 枚の絵をうまく選ぶことで，「エゴイ展」の華やかさをできるだけ大きくしたい．

N 枚の絵の情報と廊下に残す絵の枚数が与えられたとき，条件を満たすような絵の残し方が存在するか判定し，もし存在する場合は，「エゴイ展」の華やかさの最大値を求めるプログラムを作成せよ．

制約

• 1 ≦ N ≦ 100000．
• 1 ≦ M ≦ N．
• 1 ≦ D ≦ 1000000000．
• 1 ≦ X_i ≦ 1000000000 (1 ≦ i ≦ N)．
• X_i ≠ X_j (1 ≦ i < j ≦ N)．
• 1 ≦ V_i ≦ 1000000000 (1 ≦ i ≦ N)．
• 入力される値はすべて整数である．

入力

入力は以下の形式で標準入力から与えられる．
N M D
X₁ V₁
X₂ V₂
:
X_N V_N

出力

条件を満たすような絵の残し方が存在しない場合，標準出力に -1 を 1 行で出力せよ．

条件を満たすような絵の残し方が存在する場合，標準出力に，「エゴイ展」の華やかさの最大値を 1 行で出力せよ．

入出力例

入力例 1

3 1 34
10 250
30 200
50 500

出力例 1

500

絵 3 のみを残した場合，「エゴイ展」の華やかさは 500 となる．華やかさを 500 より大きくすることはできないため，500 を出力する．

入力例 2

4 4 10
21 160
32 270
11 115
44 205

出力例 2

115

すべての絵を残すことができ，「エゴイ展」の華やかさは 115 となる．

入力例 3

4 4 14
21 160
32 270
11 115
44 205

出力例 3

-1

どの 2 つの絵の間も 14 メートル以上離れているように絵を残すことはできない．したがって，－1 を出力する．

入力例 4

6 3 4
4 2
5 2
2 1
9 2
1 1
7 2

出力例 4

1

入力例 5

15 6 129
185 2821
683 3312
101 3406
485 2120
671 1992
869 2555
872 3123
237 2970
351 2374
996 2090
729 2686
375 2219
820 3085
511 3217
924 4229

出力例 5

2219

---