問題文

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)
• 入力は全て整数

入力例 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