题目描述

你有 $n$ 个物品，每个物品有一个颜色 $c_i (1 ≤ c_i ≤ K)$ 和权值 $v_i$。你需要选出 $x$ 个物品，满足若颜色 $i$ 的物品被选中，那么颜色 $i$ 至少存在两个物品被选中，并且最大化总权值和。你需要对 $x = 1\dots n$ 均求出答案。如果无解，则输出 $-1$ 。

输入格式

输入第一行两个 $n$， $K$。

接下来 $n$ 行，每行两个整数 $c_i$， $v_i$。

输出格式

输出共 $n$ 行，每 $i$ 行表示 $x =$ i 时的答案。若无解，输出 $-1$。

输入输出样例 #1

输入 #1

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

输出 #1

-1
9
6
14
15

输入输出样例 #2

输入 #2

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

输出 #2

-1
9
12
12
15

输入输出样例 #3

输入 #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

输入 #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

说明/提示

对于所有数据， $1 ≤ n ≤ 2 \times 10^5, 1 ≤ K ≤\frac n 2,1\le c_i\le K, 0 \le v_i \le 10^9$ ,保证对于每种出现在了输入中的颜色，至少存在 $2$ 个该颜色的物品。