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