22018번 - 展覧会 2 (Exhibition 2) 서브태스크다국어

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

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

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

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

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

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

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

N M D
X1 V1
X2 V2
:
XN VN

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

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

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