配点 : $1200$ 点

問題文

$N$ 個の宝石があり、$1$ から $N$ までの番号がついています。 それぞれの宝石の色は $1$ 以上 $K$ 以下の整数で表され、宝石 $i$ の色は $C_i$ です。 また、それぞれの宝石には価値が定まっており、宝石 $i$ の価値は $V_i$ です。

すぬけ君はこれらの宝石のうちいくつかを選んで展示したいです。 ただし、選んだ宝石の集合は、次の条件を満たす必要があります。

• 選ばれたどの宝石についても、同じ色の選ばれた宝石がそれのほかに $1$ つ以上存在する。

$1 \leq x \leq N$ を満たすすべての整数 $x$ について、ちょうど $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$
• どの色についても、その色の宝石が $2$ つ以上存在する。
• 入力される値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $K$

$C_1$ $V_1$

$C_2$ $V_2$

$:$

$C_N$ $V_N$

出力

$N$ 行出力せよ。 $i$ 行目に、ちょうど $i$ 個の宝石を選ぶことが可能な場合は、その場合の選んだ宝石の価値の総和としてあり得る最大の値を出力し、不可能な場合は $-1$ を出力せよ。

5 2
1 1
1 2
1 3
2 4
2 5

-1
9
6
14
15

ちょうど $1$ 個の宝石を選ぶことはできません。

ちょうど $2$ 個の宝石を選ぶ場合は、宝石 $4,5$ を選ぶことで価値の総和を最大化できます。

ちょうど $3$ 個の宝石を選ぶ場合は、宝石 $1,2,3$ を選ぶことで価値の総和を最大化できます。

ちょうど $4$ 個の宝石を選ぶ場合は、宝石 $2,3,4,5$ を選ぶことで価値の総和を最大化できます。

ちょうど $5$ 個の宝石を選ぶ場合は、宝石 $1,2,3,4,5$ を選ぶことで価値の総和を最大化できます。

5 2
1 1
1 2
2 3
2 4
2 5

-1
9
12
12
15

8 4
3 2
2 3
4 5
1 7
3 11
4 13
1 17
2 19

-1
24
-1
46
-1
64
-1
77

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

-1
145
173
285
318
398
431
491
524
576
609
634
653
666
678