#P10526. [2021年联测]珠宝
[2021年联测]珠宝
珠宝(jewels)
问题描述
你有个珠宝,编号是 到。第 个珠宝有颜色 和价值。
你要选择一些珠宝,满足对于任意选择了的珠宝,都有至少一个其它选择了的珠宝和这个珠宝颜色相同。
对于每个求出,是否存在一种选择珠宝的方案满足选了恰好个珠宝,如果没有,输出,否则输出这些方案中最大的珠宝价值总和(不输出具体选择)。
输入格式
第一行输入两个正整数 和,表示珠宝数和颜色数。
接下来行每行两个正整数 和,描述一个珠宝。
输出格式
行,第 行输出选恰好个珠宝的答案。
样例 1 输入
5 2
1 1
1 2
1 3
2 4
2 5
样例 1 输出
-1
9
6
14
15
样例 2 输入
15 5
3 87
1 25
1 27
3 58
2 85
5 19
5 39
1 58
3 12
4 13
5 54
4 100
2 33
5 13
2 55
样例 2 输出
-1
145
173
285
318
398
431
491
524
576
609
634
653
666
678
数据规模与约定
对于所有数据,保证 $1 \leq N \leq2 \times10^{5} , 1 \leq K \leq\lfloor\frac{N} {2} \rfloor, 1 \leq C_{i} \leq K , 1 \leq V_{i} \leq10^{9} .$。
| 子任务编号 | 分值 | 其他限制 |
|---|---|---|
| 1 | ||
| 2 | 10 | |
| 无 |