A - Organizing the Bookshelf Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

高橋君は、自分の本棚を整理しながら、読み直す本を選ぼうとしています。

本棚には N 冊の本があり、i 番目の本（1 \leq i \leq N）には「これまでに読んだ回数」を表す値 C_i と「満足度」を表す値 D_i が記録されています。

高橋君は、これまでに読んだ回数が少ない本を優先的に読み直そうと考えました。具体的には、読んだ回数が K 回以下の本を全て読み直す候補として選び出し、それらの満足度の合計を知りたいと思っています。

N 冊の本の中から、読んだ回数が K 回以下であるものを全て選んだときの、満足度の合計値を求めてください。該当する本が 1 冊もない場合、合計値は 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
  • 1 行目には、本の冊数を表す整数 N と、読んだ回数の上限を表す整数 K が、スペース区切りで与えられる。
  • 続く N 行のうち i 行目（1 \leq i \leq N）には、i 番目の本のこれまでに読んだ回数 C_i と満足度 D_i が、スペース区切りで与えられる。

出力

読んだ回数が K 回以下である本の満足度の合計値を 1 行で出力せよ。該当する本がない場合は 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

Score : 200 pts

Problem Statement

Takahashi is trying to choose books to reread while organizing his bookshelf.

There are N books on the bookshelf, and for the i-th book (1 \leq i \leq N), a value C_i representing "the number of times it has been read so far" and a value D_i representing "satisfaction" are recorded.

Takahashi decided to prioritize rereading books that he has read fewer times. Specifically, he wants to select all books that have been read K times or fewer as candidates for rereading, and he wants to know the total satisfaction of those books.

From the N books, find the total satisfaction of all books that have been read K times or fewer. If there are no such books, the total is 0.

Constraints

  • 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)
  • All inputs are integers
  • It is guaranteed that the answer is at most 2 \times 10^{14}

Input

N K
C_1 D_1
C_2 D_2
\vdots
C_N D_N
  • The first line contains an integer N representing the number of books and an integer K representing the upper limit on the number of times read, separated by a space.
  • In the following N lines, the i-th line (1 \leq i \leq N) contains the number of times the i-th book has been read C_i and its satisfaction D_i, separated by a space.

Output

Output in one line the total satisfaction of books that have been read K times or fewer. If there are no such books, output 0.

Sample Input 1

5 2
1 10
3 20
0 15
2 30
5 25

Sample Output 1

55

Sample Input 2

4 1
5 100
3 200
10 50
2 300

Sample Output 2

0

Sample Input 3

10 5
3 120
7 250
5 80
0 300
12 60
4 150
6 90
1 200
9 110
5 170

Sample Output 3

1020

Sample Input 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

Sample Output 4

7899999999

Sample Input 5

1 0
0 1

Sample Output 5

1