AT_wtf22_day2_c Jewel Pairs
题目描述
有 $N$ 个宝石，编号为 $1$ 到 $N$。宝石 $i$ 的颜色为 $C_i$，价值为 $V_i$。其中颜色用 $1$ 到 $N$ 之间的整数表示。
两个宝石的配对 $(i,j)$ 当且仅当满足以下两个条件时被称为**好的**配对：
- $C_i \neq C_j$
- $V_i + V_j \leq L$
你需要从 $N$ 个宝石中选出若干个好的配对。每个宝石最多只能属于一个配对，但允许存在不属于任何配对的宝石。
请计算所选配对中所有宝石的价值总和的最大可能值。
输入格式
输入通过标准输入给出，格式如下：
> $N$ $L$
> $C_1$ $V_1$
> $C_2$ $V_2$
> $\vdots$
> $C_N$ $V_N$
输出格式
输出答案。
说明/提示
### 约束条件
- $1 \leq N \leq 250000$
- $1 \leq L \leq 10^9$
- $1 \leq C_i \leq N$
- $0 \leq V_i \leq L$
- 所有输入值均为整数。
### 样例解释 1
配对 $(1,2)$ 不满足第一个条件，因此不是好的配对。配对 $(1,4)$ 不满足第二个条件。此样例的最优解是选择配对 $(2,3)$。
### 样例解释 2
此样例的最优解是选择配对 $(1,5)$ 和 $(2,3)$。