题目描述
Problem Description
There are $ N $ jewels, numbered from $ 1 $ to $ N $. Each jewel is represented by an integer color between $ 1 $ and $ K $, where the color of jewel $ i $ is $ C_i $. Each jewel also has a value, where the value of jewel $ i $ is $ V_i $.
Snuke wants to select some of these jewels to display. However, the set of selected jewels must satisfy the following condition:
- For every selected jewel, there must be at least one other selected jewel of the same color.
For every integer $ x $ satisfying $1 \leq x \leq N$, determine whether it is possible to select exactly $ x $ jewels. If it is possible, find the maximum possible total value of the selected jewels.
Input Format
The input is given from the standard input in the following format:
$ N $ $ K $ $ C_1 $ $ V_1 $ $ C_2 $ $ V_2 $ $ : $ $ C_N $ $ V_N $
Output Format
Output $ N $ lines. On the $ i $-th line, if it is possible to select exactly $ i $ jewels, output the maximum possible total value of the selected jewels. If it is not possible, output $ -1 $.
Sample Input and Output
Sample Input #1
5 2
1 1
1 2
1 3
2 4
2 5
Sample Output #1
-1
9
6
14
15
Sample Input #2
5 2
1 1
1 2
2 3
2 4
2 5
Sample Output #2
-1
9
12
12
15
Sample Input #3
8 4
3 2
2 3
4 5
1 7
3 11
4 13
1 17
2 19
Sample Output #3
-1
24
-1
46
-1
64
-1
77
Sample Input #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
Sample Output #4
-1
145
173
285
318
398
431
491
524
576
609
634
653
666
678
Notes/Hints
Constraints
- $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$
- For every color, there are at least two jewels of that color.
- All input values are integers.
Sample Explanation 1
It is not possible to select exactly $ 1 $ jewel. For exactly $ 2 $ jewels, selecting jewels $ 4 $ and $ 5 $ maximizes the total value. For exactly $ 3 $ jewels, selecting jewels $ 1, 2, $ and $ 3 $ maximizes the total value. For exactly $ 4 $ jewels, selecting jewels $ 2, 3, 4, $ and $ 5 $ maximizes the total value. For exactly $ 5 $ jewels, selecting jewels $ 1, 2, 3, 4, $ and $ 5 $ maximizes the total value.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分