分数: 200 分
问题陈述
高桥一边整理书架,一边尝试选择要重读的书籍。
有 N 书架上的书,以及 i第本书(1 \leq i \leq N),一个值 C_i 代表“到目前为止已被读取的次数”和一个值 记录代表“满意”的 D_i 。
高桥决定优先重读他读过次数较少的书籍。具体来说,他想选择所有已读过的书 作为重读候选者的 K 次或更少,他想知道这些书的总体满意度。
从 N 书籍,找到所有读过的书的总满意度 K 次或更少。如果没有此类书籍,总数为 0.
约束
- 1 \leq N \leq 2 \times 10^5
- 0 \leq K \leq 10^9
- 0 \leq C_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq D_i \leq 10^9 (1 \leq i \leq N)
- 所有输入均为整数
- 保证答案最多是 2 \times 10^{14}
输入
N K C_1 D_1 C_2 D_2 \vdots C_N D_N
- 第一行包含一个整数 N 代表书籍数量和一个整数 K 代表读取次数上限,以空格分隔。
- 如下 N 行, i- 第行 (1 \leq i \leq N) 包含的次数 i第本书已读 C_i 及其满意度 D_i,用空格分隔。
输出
一行输出已读过的书籍的总满意度 K 次或更少。如果没有这样的书,则输出 0.
示例输入 1
5 2 1 10 3 20 0 15 2 30 5 25
示例输出 1
55
示例输入 2
4 1 5 100 3 200 10 50 2 300
示例输出 2
0
示例输入 3
10 5 3 120 7 250 5 80 0 300 12 60 4 150 6 90 1 200 9 110 5 170
示例输出 3
1020
示例输入 4
20 100 50 1000000000 101 500000000 99 800000000 200 300000000 0 999999999 100 750000000 150 600000000 30 450000000 75 200000000 110 350000000 1 900000000 88 100000000 100 550000000 250 400000000 99 650000000 1000000000 1000000000 45 700000000 102 850000000 100 500000000 60 300000000
示例输出 4
7899999999
示例输入 5
1 0 0 1
示例输出 5
1