#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define MAXN 200005
#define eps 1e-10
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
	res = 0;T f = 1;char c = getchar();
	while(c < '0' || c > '9') {
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9') {
		res = res * 10 + c - '0';
		c = getchar();
	}
	res *= f;
}
template<class T>
void out(T x) {
	if(x < 0) {x = -x;putchar('-');}
	if(x >= 10) {
		out(x / 10);
	}
	putchar('0' + x % 10);
}
struct node {
	int pos;int64 v;
	friend bool operator < (const node &a,const node &b) {
		return a.v > b.v || (a.v == b.v && a.pos < b.pos);
	}
};
set<node> S,D,T,CD,CS;
vector<int64> ver[MAXN];
int p[MAXN],N,K;
int64 ans,rec[MAXN];
void Choose_one() {
	node t = *S.begin();S.erase(S.begin());CS.insert(t);
	ans += t.v;
	++p[t.pos];
	if(p[t.pos] <= ver[t.pos].size() - 1) {
		S.insert((node){t.pos,ver[t.pos][p[t.pos]]});
	}
}
void Delete_one() {
	node t = *(--CS.end());CS.erase(--CS.end());
	ans -= t.v;
	if(p[t.pos] <= ver[t.pos].size() - 1) {
		S.erase((node){t.pos,ver[t.pos][p[t.pos]]});
	}
	S.insert(t);--p[t.pos];
}
void Choose_two() {
	node t = *D.begin();D.erase(D.begin());CD.insert(t);
	ans += t.v;
	p[t.pos] = 2;
	if(p[t.pos] <= ver[t.pos].size() - 1) {
		S.insert((node){t.pos,ver[t.pos][p[t.pos]]});
	}
	if(ver[t.pos].size() >= 3) {
		T.erase((node){t.pos,ver[t.pos][0] + ver[t.pos][1] + ver[t.pos][2]});
	}
}
void Delete_two() {
	node t = *(--CD.end());CD.erase(--CD.end());
	S.erase((node){t.pos,ver[t.pos][p[t.pos]]});
	D.insert((node){t.pos,ver[t.pos][0] + ver[t.pos][1]});
	if(ver[t.pos].size() >= 3) {
		T.insert((node){t.pos,ver[t.pos][0] + ver[t.pos][1] + ver[t.pos][2]});
	}
	ans -= t.v;
}
void Choose_three() {
	node t = *T.begin();T.erase(T.begin());
	ans += t.v;
	p[t.pos] = 3;
	D.erase((node){t.pos,ver[t.pos][0] + ver[t.pos][1]});
	CD.insert((node){t.pos,ver[t.pos][0] + ver[t.pos][1]});
	CS.insert((node){t.pos,ver[t.pos][2]});
	if(p[t.pos] <= ver[t.pos].size() - 1) {
		S.insert((node){t.pos,ver[t.pos][p[t.pos]]});
	}
}
void Solve() {
	read(N);read(K);
	int c;int64 v;
	for(int i = 1 ; i <= N ; ++i) {
		read(c);read(v);ver[c].pb(v);
	}
	for(int i = 1 ; i <= K ; ++i) {
		sort(ver[i].begin(),ver[i].end(),[](int64 a,int64 b){return a > b;});
	}
	for(int i = 1 ; i <= K ; ++i) {
		if(ver[i].size()) {
			D.insert((node){i,ver[i][0] + ver[i][1]});
			if(ver[i].size() >= 3) T.insert((node){i,ver[i][0] + ver[i][1] + ver[i][2]});
		}
	}
	rec[1] = -1;ans = 0;
	puts("-1");
	for(int i = 2 ; i <= N ; ++i) {
		if(rec[i - 1] == -1) {
			Choose_two();
			rec[i] = ans;
		}
		else {
			int64 w[3] = {-1,-1,-1};
			if(S.size()) {
				w[0] = ans + (*S.begin()).v;
			}
			if(CS.size() && D.size()) {
				w[1] = ans - (*(--CS.end())).v + (*D.begin()).v;
			}
			if(CD.size() && T.size()) {
				w[2] = ans - (*(--CD.end())).v + (*T.begin()).v;
			}
			if(w[0] < 0 && w[1] < 0 && w[2] < 0) {rec[i] = -1;}
			else {
				if(w[0] >= max(w[1],w[2])) {Choose_one();}
				else if(w[1] >= max(w[0],w[2])) {Delete_one();Choose_two();}
				else {Delete_two();Choose_three();}
				rec[i] = ans;
			}
			while(1) {
				if(!D.size()) break;
				if(!CD.size()) break;
				node t = *(--CD.end());
				node s = *D.begin();
				if(p[t.pos] == 2) {
					if(s.v > t.v) {
						Delete_two();Choose_two();
					}
					else break;
				}
				else break;
				rec[i] = ans;
			}
		}
		out(rec[i]);enter;
	}
}
int main() {
#ifdef ivorysi
	freopen("f1.in","r",stdin);
#endif
	Solve();
}

### Prompt

Please create a solution in cpp to 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 <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define MAXN 200005
#define eps 1e-10
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
	res = 0;T f = 1;char c = getchar();
	while(c < '0' || c > '9') {
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9') {
		res = res * 10 + c - '0';
		c = getchar();
	}
	res *= f;
}
template<class T>
void out(T x) {
	if(x < 0) {x = -x;putchar('-');}
	if(x >= 10) {
		out(x / 10);
	}
	putchar('0' + x % 10);
}
struct node {
	int pos;int64 v;
	friend bool operator < (const node &a,const node &b) {
		return a.v > b.v || (a.v == b.v && a.pos < b.pos);
	}
};
set<node> S,D,T,CD,CS;
vector<int64> ver[MAXN];
int p[MAXN],N,K;
int64 ans,rec[MAXN];
void Choose_one() {
	node t = *S.begin();S.erase(S.begin());CS.insert(t);
	ans += t.v;
	++p[t.pos];
	if(p[t.pos] <= ver[t.pos].size() - 1) {
		S.insert((node){t.pos,ver[t.pos][p[t.pos]]});
	}
}
void Delete_one() {
	node t = *(--CS.end());CS.erase(--CS.end());
	ans -= t.v;
	if(p[t.pos] <= ver[t.pos].size() - 1) {
		S.erase((node){t.pos,ver[t.pos][p[t.pos]]});
	}
	S.insert(t);--p[t.pos];
}
void Choose_two() {
	node t = *D.begin();D.erase(D.begin());CD.insert(t);
	ans += t.v;
	p[t.pos] = 2;
	if(p[t.pos] <= ver[t.pos].size() - 1) {
		S.insert((node){t.pos,ver[t.pos][p[t.pos]]});
	}
	if(ver[t.pos].size() >= 3) {
		T.erase((node){t.pos,ver[t.pos][0] + ver[t.pos][1] + ver[t.pos][2]});
	}
}
void Delete_two() {
	node t = *(--CD.end());CD.erase(--CD.end());
	S.erase((node){t.pos,ver[t.pos][p[t.pos]]});
	D.insert((node){t.pos,ver[t.pos][0] + ver[t.pos][1]});
	if(ver[t.pos].size() >= 3) {
		T.insert((node){t.pos,ver[t.pos][0] + ver[t.pos][1] + ver[t.pos][2]});
	}
	ans -= t.v;
}
void Choose_three() {
	node t = *T.begin();T.erase(T.begin());
	ans += t.v;
	p[t.pos] = 3;
	D.erase((node){t.pos,ver[t.pos][0] + ver[t.pos][1]});
	CD.insert((node){t.pos,ver[t.pos][0] + ver[t.pos][1]});
	CS.insert((node){t.pos,ver[t.pos][2]});
	if(p[t.pos] <= ver[t.pos].size() - 1) {
		S.insert((node){t.pos,ver[t.pos][p[t.pos]]});
	}
}
void Solve() {
	read(N);read(K);
	int c;int64 v;
	for(int i = 1 ; i <= N ; ++i) {
		read(c);read(v);ver[c].pb(v);
	}
	for(int i = 1 ; i <= K ; ++i) {
		sort(ver[i].begin(),ver[i].end(),[](int64 a,int64 b){return a > b;});
	}
	for(int i = 1 ; i <= K ; ++i) {
		if(ver[i].size()) {
			D.insert((node){i,ver[i][0] + ver[i][1]});
			if(ver[i].size() >= 3) T.insert((node){i,ver[i][0] + ver[i][1] + ver[i][2]});
		}
	}
	rec[1] = -1;ans = 0;
	puts("-1");
	for(int i = 2 ; i <= N ; ++i) {
		if(rec[i - 1] == -1) {
			Choose_two();
			rec[i] = ans;
		}
		else {
			int64 w[3] = {-1,-1,-1};
			if(S.size()) {
				w[0] = ans + (*S.begin()).v;
			}
			if(CS.size() && D.size()) {
				w[1] = ans - (*(--CS.end())).v + (*D.begin()).v;
			}
			if(CD.size() && T.size()) {
				w[2] = ans - (*(--CD.end())).v + (*T.begin()).v;
			}
			if(w[0] < 0 && w[1] < 0 && w[2] < 0) {rec[i] = -1;}
			else {
				if(w[0] >= max(w[1],w[2])) {Choose_one();}
				else if(w[1] >= max(w[0],w[2])) {Delete_one();Choose_two();}
				else {Delete_two();Choose_three();}
				rec[i] = ans;
			}
			while(1) {
				if(!D.size()) break;
				if(!CD.size()) break;
				node t = *(--CD.end());
				node s = *D.begin();
				if(p[t.pos] == 2) {
					if(s.v > t.v) {
						Delete_two();Choose_two();
					}
					else break;
				}
				else break;
				rec[i] = ans;
			}
		}
		out(rec[i]);enter;
	}
}
int main() {
#ifdef ivorysi
	freopen("f1.in","r",stdin);
#endif
	Solve();
}

```