配点: 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