009 - 展覧会 2 (Exhibition 2)

時間制限 1 秒 / メモリ制限 1024 MB / 得点 100 / x 0 /

TLE
1sec
MLE
1024MB
得点
100

問題

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

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

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

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

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

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

制約

  • 1 ≦ N ≦ 100 000．
  • 1 ≦ M ≦ N．
  • 1 ≦ D ≦ 1 000 000 000．
  • 1 ≦ Xi ≦ 1 000 000 000 (1 ≦ i ≦ N)．
  • Xi ≠ Xj (1 ≦ i < j ≦ N)．
  • 1 ≦ Vi ≦ 1 000 000 000 (1 ≦ i ≦ N)．
  • 入力される値はすべて整数である．

小課題

  1. (3 点) M = 1．
  2. (12 点) M = N．
  3. (19 点) N ≦ 15．
  4. (17 点) N ≦ 1 000，Vi ≦ 2 (1 ≦ i ≦ N)．
  5. (22 点) N ≦ 1 000．
  6. (27 点) 追加の制約はない．

入力

入力は以下の形式で標準入力から与えられる．
N M D
X1 V1
X2 V2
:
XN VN

出力

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

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

入出力例

入力例1

3 1 34
10 250
30 200
50 500

出力例1

500

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

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

入力例2

4 4 10
21 160
32 270
11 115
44 205

出力例2

115

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

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

入力例3

4 4 14
21 160
32 270
11 115
44 205

出力例3

-1

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

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

入力例4

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

出力例4

1

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

入力例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

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