← 返回题目列表

AtCoder · wtf22_day2_c

C. 珠宝对

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

分数: 2000 点

问题陈述

有 N 编号的宝石 1 to N。 宝石 i 有颜色 C_i 和一个值 V_i。 这里,颜色用整数表示,从 1 通过 N.

两颗宝石的一对 (i,j) 据说是 好 当且仅当它们满足以下条件时为一对:

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

你将从这些宝石中组成若干个好对。 N 同一颗宝石不能属于多个对,但某些宝石不属于任何对是可以的。

找出所有对中宝石的最大可能总价值。

约束

  • 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,4) 这不好,因为第二个条件不满足。

在这种情况下,制作这一对是最优的。 (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