問題文

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

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

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

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

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

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

制約

• 1 \leqq N \leqq 100\,000．
• 1 \leqq M \leqq N．
• 1 \leqq D \leqq 1\,000\,000\,000．
• 1 \leqq X_i \leqq 1\,000\,000\,000 (1 \leqq i \leqq N)．
• X_i \neq X_j (1 \leqq i < j \leqq N)．
• 1 \leqq V_i \leqq 1\,000\,000\,000 (1 \leqq i \leqq N)．
• 入力される値はすべて整数である．

小課題

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

採点に関する注意

すべての提出はジャッジシステム上で採点される．

提出されたソースコードは，小課題に対応するすべての採点用入力データについて正しい結果を返したとき，その小課題について正解となる．

各提出の得点は，提出されたソースコードが正解した小課題の得点の合計である．

この課題の得点は，この課題に対するすべての提出の得点の最大値である．

現在の得点は「提出結果」タブの「自分の得点状況」から確認できる．

入力例 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 の制約を満たす．