← 返回题目列表

AtCoder · nikkei2019_qual_f

F. 珠宝

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

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