#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <climits>
#include <cmath>
#include <utility>
#include <string>
#include <cstring>
#include <functional>

using namespace std;

const int maxn = 200020;

int n, K;

struct Jewel
{
	int c;
	long long v;

	Jewel(int cc, long long vv) {
		c = cc;
		v = vv;
	}

	bool operator<(const Jewel &b) const {
		if (v == b.v)
			return c < b.c;
		else
			return v > b.v;
	}
};

const long long INF = ((long long)1) << 60;

int nums[maxn>>1];
vector<int> kinds[maxn>>1];
multiset<Jewel> x, y, z;

void mymin(long long &a, long long b) {
	if (a > b)
		a = b;
}

void mymax(long long &a, long long b) {
	if (a < b)
		a = b;
}

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n >> K;

	for (int i = 0; i < n; ++i) {
		int c;
		long long v;
		cin >> c >> v;
		--c;

		kinds[c].push_back(v);
	}

	vector<Jewel> jewels;

	for (int i = 0; i < K; ++i)
		if (!kinds[i].empty()) {
			vector<int> &v = kinds[i];

			sort(v.begin(), v.end());
			reverse(v.begin(), v.end());

			// for (int j = 0; j < v.size(); ++j)
			// 	printf("%d ", v[j]);
			// printf("\n");

			jewels.push_back(Jewel(i, v[0] + v[1]));
			jewels.push_back(Jewel(i, v[0] + v[1]));

			for (int j = 2; j < v.size(); ++j)
				jewels.push_back(Jewel(i, v[j]<<1));

			y.insert(Jewel(i, v[0] + v[1]));

			if (v.size() >= 3)
				z.insert(Jewel(i, ((long long)v[0] + v[1] + v[2])<<1));
		}

	sort(jewels.begin(), jewels.end());

	long long min_value = INF, min_pair = INF, sum = 0;

	for (int i = 0; i < n; ++i) {
		long long ans = -2;
		int c = jewels[i].c;
		long long v = jewels[i].v;

		// printf("%d:%d %lld\n", i, c, v);

		if (nums[c] == 0) {
			if (!x.empty())
				mymax(ans, sum + x.begin()->v);
			if (!y.empty())
				mymax(ans, sum + y.begin()->v * 2 - min_value);
			if (!z.empty())
				mymax(ans, sum + z.begin()->v - min_pair);

			y.erase(y.find(jewels[i]));
			
			if (kinds[c].size() >= 3) {
				Jewel tmp(c, ((long long)kinds[c][0] + kinds[c][1] + kinds[c][2])<<1);
				z.erase(z.find(tmp));
			}

		} else {
			ans = sum + v;
			if (nums[c] == 1) {
				for (int j = 2; j < kinds[c].size(); ++j)
					x.insert(Jewel(c, kinds[c][j]<<1));

				mymin(min_pair, v << 1);
			} else {
				x.erase(x.find(jewels[i]));
				mymin(min_value, v);
			}
		}

		++nums[c];
		sum += v;

		cout << ans/2 << endl;
	}

	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
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <climits>
#include <cmath>
#include <utility>
#include <string>
#include <cstring>
#include <functional>

using namespace std;

const int maxn = 200020;

int n, K;

struct Jewel
{
	int c;
	long long v;

	Jewel(int cc, long long vv) {
		c = cc;
		v = vv;
	}

	bool operator<(const Jewel &b) const {
		if (v == b.v)
			return c < b.c;
		else
			return v > b.v;
	}
};

const long long INF = ((long long)1) << 60;

int nums[maxn>>1];
vector<int> kinds[maxn>>1];
multiset<Jewel> x, y, z;

void mymin(long long &a, long long b) {
	if (a > b)
		a = b;
}

void mymax(long long &a, long long b) {
	if (a < b)
		a = b;
}

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n >> K;

	for (int i = 0; i < n; ++i) {
		int c;
		long long v;
		cin >> c >> v;
		--c;

		kinds[c].push_back(v);
	}

	vector<Jewel> jewels;

	for (int i = 0; i < K; ++i)
		if (!kinds[i].empty()) {
			vector<int> &v = kinds[i];

			sort(v.begin(), v.end());
			reverse(v.begin(), v.end());

			// for (int j = 0; j < v.size(); ++j)
			// 	printf("%d ", v[j]);
			// printf("\n");

			jewels.push_back(Jewel(i, v[0] + v[1]));
			jewels.push_back(Jewel(i, v[0] + v[1]));

			for (int j = 2; j < v.size(); ++j)
				jewels.push_back(Jewel(i, v[j]<<1));

			y.insert(Jewel(i, v[0] + v[1]));

			if (v.size() >= 3)
				z.insert(Jewel(i, ((long long)v[0] + v[1] + v[2])<<1));
		}

	sort(jewels.begin(), jewels.end());

	long long min_value = INF, min_pair = INF, sum = 0;

	for (int i = 0; i < n; ++i) {
		long long ans = -2;
		int c = jewels[i].c;
		long long v = jewels[i].v;

		// printf("%d:%d %lld\n", i, c, v);

		if (nums[c] == 0) {
			if (!x.empty())
				mymax(ans, sum + x.begin()->v);
			if (!y.empty())
				mymax(ans, sum + y.begin()->v * 2 - min_value);
			if (!z.empty())
				mymax(ans, sum + z.begin()->v - min_pair);

			y.erase(y.find(jewels[i]));
			
			if (kinds[c].size() >= 3) {
				Jewel tmp(c, ((long long)kinds[c][0] + kinds[c][1] + kinds[c][2])<<1);
				z.erase(z.find(tmp));
			}

		} else {
			ans = sum + v;
			if (nums[c] == 1) {
				for (int j = 2; j < kinds[c].size(); ++j)
					x.insert(Jewel(c, kinds[c][j]<<1));

				mymin(min_pair, v << 1);
			} else {
				x.erase(x.find(jewels[i]));
				mymin(min_value, v);
			}
		}

		++nums[c];
		sum += v;

		cout << ans/2 << endl;
	}

	return 0;
}
```