No.448 ゆきこーだーの雨と雪 (3)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / タグ : / 解いたユーザー数 30
作問者 : りあん🐺☔️⛄️りあん🐺☔️⛄️ / テスター : 3737

3 ProblemId : 1430 / 出題時の順位表

問題文

Ameくんは, またまた「ゆきこーだー」を運営しているお姉さんのYukiさんのお手伝いをすることになる...はずでした.

しかし, コンテスト当日にYukiさんが体調を崩してしまいました!

そこで, 今回はAmeくんがコンテストの運営を行うことにしました!


...とは言ったものの, Ameくんは今までYukiさんのお手伝いしかしたことがないので, 一人でコンテストを開くのはとても難しいです.

コンテストを開くのには, コンテスト中やコンテスト前後の決まった時刻に決まった処理をしなければならないのですが, それぞれの処理は, Ameくんから見た「難しさ」が違います.

Ameくんは自信がないので, そこまで難しい処理をやりたくはありません.

そこで, 難しい処理に関してはYukiさんを起こしてYukiさんにお願いすることにしました. ただ, あまりYukiさんに無理はさせられないので, 一度起こしてからもう一度起こすまで必ず一定時間以上空けることにしました.

Ameくんはその制約の中で, まずAmeくんが行う処理の中で一番難しいものの難しさを最小化し, かつその中でAmeくんが行う処理全体の難しさの総和を最小化したいと思いました.


そのようにしたときの, Ameくんが行う処理の中で一番難しいものの難しさと, Ameくんが行う処理全体の難しさの総和を求めてください.

なお, Ameくんが処理を一つも行わなくてよい場合はどちらも $0$ を出力してください.


なお, Yukiさんは時刻 $0$ においてすでに十分な時間連続して寝ているものとします.

また, Yukiさんは任意の処理を一瞬で行い, もう一度眠りにつくまでの時間は無視できるものとします.

入力

$N \ K$
$T_1 \ D_1$
$T_2 \ D_2$
 $:$
$T_N \ D_N$

1行目に, 行わなければならない処理の数 $N$ とYukiさんを連続して寝かせてあげたい時間 $K$ が与えられます.

続いて2行目から $N$ 行の間, 各処理の情報が与えられます.

2行目以降の第 $i \ (1 \leq i \leq N)$ 行目には, 処理 $i$ を行う時刻 $T_i$ と処理 $i$ の難しさ $D_i$ が空白区切りで与えられます.

入力は全て整数で, 以下の制約を満たします.

  • $1 \leq N \leq 2 \times 10^5$
  • $1 \leq K \leq 10^9$
  • $1 \leq T_1 \lt T_2 \lt \ ... \lt T_N \leq 10^9$
  • $1 \leq D_i \leq 10^9$

部分点などはありませんが, 1_small_*.in は $N, K \leq 1000, \ \ T_i \ , \ D_i \leq 10^5$ を満たします.

出力

1行目に, Ameくんが行う処理の中で一番難しいものの難しさを出力してください.

続いて2行目に, Ameくんが行う処理全体の難しさの総和を出力してください.

最後に改行してください.

サンプル

サンプル1
入力
5 3
4 5
5 6
7 7
8 4
11 4
出力
6
10

Yukiさんに1つめ, 3つめ, 5つめの処理を行ってもらうと, Ameくんが行う処理の難しさの最大値は $6$, 総和は $10$ となりこれが最適となります.

サンプル2
入力
9 1
1 1
2 10
3 100
4 1000
5 10000
6 100000
7 1000000
8 10000000
9 100000000
出力
0
0

AmeくんはYukiさんを起こすことに躊躇がないので, Ameくんが行う処理は存在しません.

Ameくんが行う処理が存在しない場合はどちらも $0$ を出力してください.

サンプル3
入力
3 8
2 6
7 9
11 5
出力
6
11

総和だけを小さくしたいならYukiさんに1つめと3つめの処理を行ってもらうことでAmeくんの行う処理の難しさの総和は $9$ になりますが,

Ameくんにとっては総和を小さくすることより最大値を小さくすることのほうが重要なので上のような答えになります.

サンプル4
入力
2 1000000000
1 1000000000
1000000000 1
出力
1
1

Yukiさんは時刻 $0$ においてすでに十分な時間連続して寝ているので, 時刻 $1$ にYukiさんを起こすことができます.

提出ページヘ