#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;
#define int64 long long
#define mp make_pair
#define pb push_back
#define fs first
#define sc second
#define sz(a) ((int) (a).size())

const int N = (int) 3e5 + 10;
int n, k, c, v;
vector<int64> who[N];
multiset<int64> triplets, singles;
vector< pair< int64, pair< int, int > > > a;

int main() {
	// freopen("input.txt", "r", stdin);
	scanf("%d%d", &n, &k);
	for (int i = 0; i < n; ++i) {
		scanf("%d%d", &c, &v), --c;
		who[c].pb(v);
	}
	for (int i = 0; i < k; ++i) {
		sort(who[i].rbegin(), who[i].rend());
		who[i][0] = who[i][1] = (who[i][0] + who[i][1]);
		for (int j = 2; j < sz(who[i]); ++j) {
			who[i][j] *= 2;
		}
	}
	for (int i = 0; i < k; ++i) {
		a.pb(mp(who[i][0], mp(i, 2)));
		for (int j = 2; j < sz(who[i]); ++j) {
			a.pb(mp(who[i][j], mp(i, 1)));
		}
		if (sz(who[i]) >= 3) {
			triplets.insert(who[i][0] + who[i][1] + who[i][2]);
		}
	}
	sort(a.rbegin(), a.rend());
	printf("-1\n");
	int64 value = 0;
	int64 last_single = -1;
	int64 last_pair = -1;
	for (int s = 2, i = 0, cur = 0; s <= n; ++s) {
		while ((i < sz(a)) && (cur + a[i].sc.sc <= s)) {
			int num = a[i].sc.fs;
			if (a[i].sc.sc == 1) {
				last_single = a[i].fs;
				cur++, value += a[i].fs;
				singles.erase(singles.find(last_single));
			} else {
				last_pair = a[i].fs * 2;
				cur += 2, value += a[i].fs * 2;
				if (sz(who[num]) >= 3) {
					triplets.erase(triplets.find(who[num][0] + who[num][1] + who[num][2]));
				}
				for (int j = 2; j < sz(who[num]); ++j) {
					singles.insert(who[num][j]);
				}
			}
			++i;
		}
		if (cur == s) {
			printf("%lld\n", value / 2);
			continue;
		}
		int64 nxt = -2;
		if (last_single != -1) {
			nxt = max(nxt, value - last_single + a[i].fs * a[i].sc.sc);
		}
		if ((last_pair != -1) && !triplets.empty()) {
			nxt = max(nxt, value - last_pair + *triplets.rbegin());
		}
		if (!singles.empty()) {
			nxt = max(nxt, value + *singles.rbegin());
		}
		printf("%lld\n", nxt / 2);
	}
	return 0;
}

### Prompt

Create a solution in Cpp for the following problem:

There are N jewels, numbered 1 to N. The color of these jewels are represented by integers between 1 and K (inclusive), and the color of Jewel i is C_i. Also, these jewels have specified values, and the value of Jewel i is V_i.

Snuke would like to choose some of these jewels to exhibit. Here, the set of the chosen jewels must satisfy the following condition:

* For each chosen jewel, there is at least one more jewel of the same color that is chosen.



For each integer x such that 1 \leq x \leq N, determine if it is possible to choose exactly x jewels, and if it is possible, find the maximum possible sum of the values of chosen jewels in that case.

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 each of the colors, there are at least two jewels of that color.
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N K
C_1 V_1
C_2 V_2
:
C_N V_N


Output

Print N lines. In the i-th line, if it is possible to choose exactly i jewels, print the maximum possible sum of the values of chosen jewels in that case, and print -1 otherwise.

Examples

Input

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


Output

-1
9
6
14
15


Input

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


Output

-1
9
12
12
15


Input

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


Output

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


Input

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


Output

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

### Response

```cpp
#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;
#define int64 long long
#define mp make_pair
#define pb push_back
#define fs first
#define sc second
#define sz(a) ((int) (a).size())

const int N = (int) 3e5 + 10;
int n, k, c, v;
vector<int64> who[N];
multiset<int64> triplets, singles;
vector< pair< int64, pair< int, int > > > a;

int main() {
	// freopen("input.txt", "r", stdin);
	scanf("%d%d", &n, &k);
	for (int i = 0; i < n; ++i) {
		scanf("%d%d", &c, &v), --c;
		who[c].pb(v);
	}
	for (int i = 0; i < k; ++i) {
		sort(who[i].rbegin(), who[i].rend());
		who[i][0] = who[i][1] = (who[i][0] + who[i][1]);
		for (int j = 2; j < sz(who[i]); ++j) {
			who[i][j] *= 2;
		}
	}
	for (int i = 0; i < k; ++i) {
		a.pb(mp(who[i][0], mp(i, 2)));
		for (int j = 2; j < sz(who[i]); ++j) {
			a.pb(mp(who[i][j], mp(i, 1)));
		}
		if (sz(who[i]) >= 3) {
			triplets.insert(who[i][0] + who[i][1] + who[i][2]);
		}
	}
	sort(a.rbegin(), a.rend());
	printf("-1\n");
	int64 value = 0;
	int64 last_single = -1;
	int64 last_pair = -1;
	for (int s = 2, i = 0, cur = 0; s <= n; ++s) {
		while ((i < sz(a)) && (cur + a[i].sc.sc <= s)) {
			int num = a[i].sc.fs;
			if (a[i].sc.sc == 1) {
				last_single = a[i].fs;
				cur++, value += a[i].fs;
				singles.erase(singles.find(last_single));
			} else {
				last_pair = a[i].fs * 2;
				cur += 2, value += a[i].fs * 2;
				if (sz(who[num]) >= 3) {
					triplets.erase(triplets.find(who[num][0] + who[num][1] + who[num][2]));
				}
				for (int j = 2; j < sz(who[num]); ++j) {
					singles.insert(who[num][j]);
				}
			}
			++i;
		}
		if (cur == s) {
			printf("%lld\n", value / 2);
			continue;
		}
		int64 nxt = -2;
		if (last_single != -1) {
			nxt = max(nxt, value - last_single + a[i].fs * a[i].sc.sc);
		}
		if ((last_pair != -1) && !triplets.empty()) {
			nxt = max(nxt, value - last_pair + *triplets.rbegin());
		}
		if (!singles.empty()) {
			nxt = max(nxt, value + *singles.rbegin());
		}
		printf("%lld\n", nxt / 2);
	}
	return 0;
}

```