分数: 1200 点
问题陈述
有 N 珠宝,编号 1 to N。 这些珠宝的颜色由之间的整数表示 1 和 K (含),以及宝石的颜色 i is C_i。 而且,这些宝石都有特定的价值,而宝石的价值 i is V_i.
Snuke 想选择其中一些珠宝来展示。 这里,所选择的珠宝套装必须满足以下条件:
- 对于每颗选定的宝石,至少还选择了一颗相同颜色的宝石。
对于每个整数 x 这样 1 \leq x \leq N,判断是否可以准确选择 x 珠宝,如果可能的话,找到在这种情况下所选珠宝的价值的最大可能总和。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq \lfloor N/2 \rfloor
- 1 \leq C_i \leq K
- 1 \leq V_i \leq 10^9
- 对于每种颜色,至少有两颗该颜色的珠宝。
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N K C_1 V_1 C_2 V_2 : C_N V_N
输出
打印 N 行。 在 i第行,如果可以准确选择 i 珠宝,打印在这种情况下所选珠宝的价值的最大可能总和,并打印 -1 否则。
示例输入 1
5 2 1 1 1 2 1 3 2 4 2 5
示例输出 1
-1 9 6 14 15
我们无法准确选择一颗宝石。
当选择两颗宝石时,当宝石 选择 4 和 5 。
当选择三颗宝石时,总价值最大化 1, 2 和 3 。
当选择四颗宝石时,总价值最大化 2, 3, 4 和 5 。
当选择正好五颗宝石时,当宝石 1, 2, 3, 4 和 5 。
示例输入 2
5 2 1 1 1 2 2 3 2 4 2 5
示例输出 2
-1 9 12 12 15
示例输入 3
8 4 3 2 2 3 4 5 1 7 3 11 4 13 1 17 2 19
示例输出 3
-1 24 -1 46 -1 64 -1 77
示例输入 4
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
示例输出 4
-1 145 173 285 318 398 431 491 524 576 609 634 653 666 678