C - Jewel Pairs Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 2000 点

問題文

1 から N までの番号がついた N 個の宝石があります． 宝石 i の色は C_i で，その価値は V_i です． ここで，色は 1 以上 N 以下の整数で表されます．

2 つの宝石の組 (i,j) は以下の条件を両方満たすとき (そしてその時のみ)，よい組と呼ばれます．

  • C_i \neq C_j
  • V_i + V_j \leq L

あなたは N 個の宝石からいくつかのよい組を作ろうとしています． 1 つの宝石が 2 個以上の組に含まれてはいけませんが，どの組にも含まれない宝石があっても構いません．

作った組に含まれるすべての宝石の価値の総和としてあり得る最大値を求めてください．

制約

  • 1 \leq N \leq 250000
  • 1 \leq L \leq 10^9
  • 1 \leq C_i \leq N
  • 0 \leq V_i \leq L
  • 入力される値はすべて整数．

入力

入力は以下の形式で標準入力から与えられる．

N L
C_1 V_1
C_2 V_2
\vdots
C_N V_N

出力

答えを出力せよ．

入力例 1

4 5
1 2
1 3
2 1
2 4

出力例 1

4

組 (1,2) は 1 番目の条件を満たさないのでよい組ではありません．

組 (1,4) は 2 番目の条件を満たさないのでよい組ではありません．

この入力例での最適な組の作り方は，組 (2,3) を作ることです．

入力例 2

5 10
3 8
4 2
1 5
1 3
1 2

出力例 2

17

この入力例での最適な組の作り方は，組 (1,5),(2,3) を作ることです．

入力例 3

9 10
8 2
7 10
1 4
3 0
5 3
3 6
2 5
5 9
5 4

出力例 3

34

入力例 4

20 1000000000
15 239276621
15 910500852
15 245532750
15 715892722
16 80707349
15 257261830
12 950300098
15 322288793
15 256358887
15 504976376
2 907119713
15 152036484
13 298766520
15 480968804
15 285187325
13 755031424
15 69837029
15 88860861
9 596982638
15 272961035

出力例 4

4704511147

Score : 2000 points

Problem Statement

There are N gems numbered 1 to N. Gem i has a color C_i and a value V_i. Here, colors are represented as integers from 1 through N.

A pair of two gems (i,j) is said to be a good pair if (and only if) they satisfy the following conditions:

  • C_i \neq C_j,
  • V_i + V_j \leq L.

You will make some number of good pairs from the N gems. A gem must not belong to multiple pairs, but it is fine if some gems belong to no pairs.

Find the maximum possible total value of all gems in your pairs.

Constraints

  • 1 \leq N \leq 250000
  • 1 \leq L \leq 10^9
  • 1 \leq C_i \leq N
  • 0 \leq V_i \leq L
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N L
C_1 V_1
C_2 V_2
\vdots
C_N V_N

Output

Print the answer.

Sample Input 1

4 5
1 2
1 3
2 1
2 4

Sample Output 1

4

The pair (1,2) is not good because the first condition is not satisfied.

The pair (1,4) is not good because the second condition is not satisfied.

In this case, it is optimal to make the pair (2,3).

Sample Input 2

5 10
3 8
4 2
1 5
1 3
1 2

Sample Output 2

17

In this case, it is optimal to make the pairs (1,5) and (2,3).

Sample Input 3

9 10
8 2
7 10
1 4
3 0
5 3
3 6
2 5
5 9
5 4

Sample Output 3

34

Sample Input 4

20 1000000000
15 239276621
15 910500852
15 245532750
15 715892722
16 80707349
15 257261830
12 950300098
15 322288793
15 256358887
15 504976376
2 907119713
15 152036484
13 298766520
15 480968804
15 285187325
13 755031424
15 69837029
15 88860861
9 596982638
15 272961035

Sample Output 4

4704511147