AT_joig2021_d 展覧会 2 (Exhibition 2)

[problemUrl]: https://atcoder.jp/contests/joig2021-open/tasks/joig2021_d JOI 美術館には，東西方向にまっすぐに伸びる廊下に $ N $ 枚の絵が飾られており，$ 1 $ から $ N $ までの番号が付けられている．絵 $ i $ ($ 1\ \leqq\ i\ \leqq\ N $) は廊下の西端から $ X_i $ メートルの位置に飾られており，その価値は $ V_i $ である． この美術館では明日から「エゴイ展」が開催される予定であり，非常に多くの来客が見込まれている．「エゴイ展」では $ M $ 枚の絵を展示する予定である． $ 2 $ つの絵が近い位置に展示されていると見づらいので，以下の条件を満たすように $ N-M $ 枚の絵を取り外し，廊下に $ M $ 枚の絵だけを残すことにした． - どの $ 2 $ つの絵についても，位置が $ D $ メートル以上離れているようにする． 展示されている $ M $ 枚の絵の価値の最小値を，「エゴイ展」の**華やかさ**とする．あなたは，廊下に残す $ M $ 枚の絵をうまく選ぶことで，「エゴイ展」の華やかさをできるだけ大きくしたい． $ N $ 枚の絵の情報と廊下に残す絵の枚数が与えられたとき，条件を満たすような絵の残し方が存在するか判定し，もし存在する場合は，「エゴイ展」の華やかさの最大値を求めるプログラムを作成せよ．

入力は以下の形式で標準入力から与えられる． > $ N $ $ M $ $ D $ $ X_1 $ $ V_1 $ $ X_2 $ $ V_2 $ $ \vdots $ $ X_N $ $ V_N $

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

### 制約 - $ 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\