048 - I will not drop out(★3) 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点: 3

問題文

N 問からなる試験があります。i 番目の問題は満点が A_i 点、部分点が B_i 点です。ここで、部分点は満点より小さく満点の半分より大きいです。つまり \frac{A_i}{2} < B_i < A_i を満たします。

E869120 君はどの問題についても 1 分かけると部分点を取ることができ、さらに 1 分かけると満点を取ることができます。

試験時間 K 分間で E869120 君が得られる合計得点の最大値を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq 2N
  • 3 \leq A_i \leq 10^9 \ (1 \leq i \leq N)
  • \frac{A_i}{2} < B_i < A_i \ (1 \leq i \leq N)
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられます。

N K
A_1 B_1
A_2 B_2
\vdots
A_N B_N

出力

E869120 君が K 分間で得られる合計得点の最大値を出力してください。


入力例 1

4 3
4 3
9 5
15 8
8 6

出力例 1

21

E869120 君は 3 問目に 2 分かけて満点 15 点を取り、4 問目に 1 分かけて部分点 6 点を取ることで、合計 21 点を得ることができます。

21 点より多く得点することはできないため、答えは 21 となります。


入力例 2

2 2
7 6
3 2

出力例 2

8

入力例 3

10 12
987753612 748826789
36950727 36005047
961239509 808587458
905633062 623962559
940964276 685396947
959540552 928301562
60467784 37828572
953685176 482123245
87983282 66762644
912605260 709048491

出力例 3

6437530406

出典

「競プロ典型90問」48日目