← 返回题目列表

AtCoder · typical90_av

048. 我不会退学(★3)

中文机器翻译题面 查看原题

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