C - School Festival Booth Planning Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

高橋君は学園祭の実行委員長です。学園祭では K 種類のカテゴリ（飲食、展示、ステージなど）が設定されており、カテゴリは 1 から K までの整数で表されます。

応募された企画は全部で N 個あり、i 番目の企画 (1 \leq i \leq N) はカテゴリ B_i に属し、集客の見込み数 D_i が設定されています。なお、企画が1つも属していないカテゴリが存在することもあります。

高橋君はこの N 個の企画の中からいくつかの企画を選んで採用します（1つも採用しなくてもよい）。ただし、各カテゴリから採用できる企画は最大1つです。すなわち、採用された企画のカテゴリはすべて異なっていなければなりません。

この条件のもとで、採用した企画の集客の見込み数の合計の最大値を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq N
  • 1 \leq B_i \leq K (1 \leq i \leq N)
  • 1 \leq D_i \leq 10^9 (1 \leq i \leq N)
  • 入力はすべて整数である。

入力

N K
B_1 D_1
B_2 D_2
\vdots
B_N D_N
  • 1 行目には、企画の個数 N と、カテゴリの種類数 K が、スペース区切りで与えられる。
  • 続く N 行の i 行目 (1 \leq i \leq N) には、i 番目の企画のカテゴリ B_i と集客の見込み数 D_i が、スペース区切りで与えられる。

出力

採用した企画の集客の見込み数の合計の最大値を 1 行で出力せよ。

入力例 1

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

出力例 1

70

入力例 2

4 4
1 100
2 200
3 300
4 400

出力例 2

1000

入力例 3

10 4
1 50
2 30
3 70
4 10
1 80
2 90
3 60
4 40
1 20
3 100

出力例 3

310

入力例 4

20 5
1 1000000000
2 999999999
3 500000000
4 750000000
5 100000000
1 999999998
2 1000000000
3 999999997
4 250000000
5 800000000
1 300000000
2 450000000
3 1000000000
4 1000000000
5 999999999
1 600000000
2 700000000
3 850000000
4 600000000
5 500000000

出力例 4

4999999999

入力例 5

1 1
1 1

出力例 5

1

Score : 300 pts

Problem Statement

Takahashi is the chairperson of the school festival organizing committee. The school festival has K categories (such as food & drink, exhibitions, stage performances, etc.), and each category is represented by an integer from 1 to K.

There are N proposed projects in total. The i-th project (1 \leq i \leq N) belongs to category B_i and has an expected visitor count of D_i. Note that there may be categories to which no project belongs.

Takahashi will select and approve some of these N projects (it is also acceptable to approve none). However, at most one project can be approved from each category. In other words, all approved projects must belong to distinct categories.

Under this condition, find the maximum possible total expected visitor count of the approved projects.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq N
  • 1 \leq B_i \leq K (1 \leq i \leq N)
  • 1 \leq D_i \leq 10^9 (1 \leq i \leq N)
  • All input values are integers.

Input

N K
B_1 D_1
B_2 D_2
\vdots
B_N D_N
  • The first line contains the number of projects N and the number of categories K, separated by a space.
  • The i-th of the following N lines (1 \leq i \leq N) contains the category B_i and the expected visitor count D_i of the i-th project, separated by a space.

Output

Print the maximum possible total expected visitor count of the approved projects in one line.

Sample Input 1

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

Sample Output 1

70

Sample Input 2

4 4
1 100
2 200
3 300
4 400

Sample Output 2

1000

Sample Input 3

10 4
1 50
2 30
3 70
4 10
1 80
2 90
3 60
4 40
1 20
3 100

Sample Output 3

310

Sample Input 4

20 5
1 1000000000
2 999999999
3 500000000
4 750000000
5 100000000
1 999999998
2 1000000000
3 999999997
4 250000000
5 800000000
1 300000000
2 450000000
3 1000000000
4 1000000000
5 999999999
1 600000000
2 700000000
3 850000000
4 600000000
5 500000000

Sample Output 4

4999999999

Sample Input 5

1 1
1 1

Sample Output 5

1