← 返回题目列表

AtCoder · awc0017_a

A. 整理书架

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

分数: 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