#include <bits/stdc++.h>

using namespace std;

#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define REV(i,n) for(ll (i) = (n) - 1;(i) >= 0;--i)
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {REP(WW,n)cerr << v[WW] << ' ';cerr << endl << endl;}
#define SHOW2d(v,WW,HH) {REP(W_,WW){REP(H_,HH)cerr << v[W_][H_] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 1000000007
#define fastcin() cin.tie(0);ios::sync_with_stdio(false)

typedef long long ll;
typedef pair<double,ll> P;

int used[111111];
int mp[111111];
ll dp[222222];
vector<vector<double>> je(111111);

int main(){
	
	REP(i,222222)dp[i] = -1;
	
	ll n,k;cin >> n >> k;
	REP(i,n){
		ll a,b;cin >> a >> b;
		je[a].PB(b);
	}
	
	vector<P> v;
	vector<P> tri;
	REP(i,111111){
		if(je[i].size() == 0)continue;
		sort(ALL(je[i]),greater<double>());
		v.EB((je[i][0] + je[i][1]) / 2.,i);
		v.EB((je[i][0] + je[i][1]) / 2.,i);
		for(int j = 2;j < je[i].size();j++){
			v.EB(je[i][j], i);
		}
		if(je[i].size() >= 3){
			tri.EB(je[i][0] + je[i][1] + je[i][2],i);
		}
	}
	
	
	sort(ALL(v),greater<P>());
	sort(ALL(tri),greater<P>());
	
	//REP(i,n)cout << "v " << v[i].FI << " " << v[i].SE << endl;
	
	vector<double> A;//二個まで
	vector<double> B;//それ以降
	double score = 0;
	int pla = 0;
	priority_queue<P> pq;
	if(tri.size())dp[3] = tri[0].FI;
	REP(i,v.size()){
		double now = v[i].FI;
		int id = v[i].SE;
		if(used[id] <= 1){
			A.PB(now);
		}
		else {
			B.PB(now);
		}
		used[id]++;
		
		if(used[id] == 2){
			//cout << "id is 2 :" << je[id].size() << endl;
			for(int j = 2;j < je[id].size();j++){
				pq.push(MP(je[id][j],id));
			}
			mp[id] = 2;
		}
		score += now;
		
		while(pla < tri.size() && used[tri[pla].SE] > 0)pla++;
		while(!pq.empty() && mp[pq.top().SE] < used[pq.top().SE]){
			mp[pq.top().SE]++;
			pq.pop();
		}
		
		if(used[id] == 1){
			if(B.size()){
			//	cout << "mel " << (ll)(score + v[i+1].FI - B.back()) << endl;
				dp[i + 1] = max(dp[i + 1], (ll)(score + v[i+1].FI - B.back()));
			}
		}
		else {
			dp[i + 1] = max(dp[i + 1], (ll)(score));
			if(pla < tri.size()){
				//cout << "!!!!!! " << (ll)(score + tri[pla].FI) << endl;
				dp[i + 4] = max(dp[i + 4], (ll)(score + tri[pla].FI));
			}
			if(!pq.empty()){
				//cout << "!!!! " << (ll)(score + pq.top().FI) << endl;
				dp[i + 2] = max(dp[i + 2], (ll)(score + pq.top().FI));
			}
			if(pla < tri.size() && !pq.empty()){
				//cout << "!!" << (ll)(score + pq.top().FI + tri[pla].FI) << endl;
				dp[i + 5] = max(dp[i + 5], (ll)(score + pq.top().FI + tri[pla].FI));
			}
		}
		//cout << "i " << i << " vFI " << v[i].FI << " vSE " << v[i].SE << " score " << score << " B " << B.size() << " pq " << pq.size() << endl;
		
	}
	
	REP(i,n)cout << dp[i+1] << endl;
	
	return 0;
}

### Prompt

Please provide a cpp coded solution to the problem described below:

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>

using namespace std;

#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define REV(i,n) for(ll (i) = (n) - 1;(i) >= 0;--i)
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {REP(WW,n)cerr << v[WW] << ' ';cerr << endl << endl;}
#define SHOW2d(v,WW,HH) {REP(W_,WW){REP(H_,HH)cerr << v[W_][H_] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 1000000007
#define fastcin() cin.tie(0);ios::sync_with_stdio(false)

typedef long long ll;
typedef pair<double,ll> P;

int used[111111];
int mp[111111];
ll dp[222222];
vector<vector<double>> je(111111);

int main(){
	
	REP(i,222222)dp[i] = -1;
	
	ll n,k;cin >> n >> k;
	REP(i,n){
		ll a,b;cin >> a >> b;
		je[a].PB(b);
	}
	
	vector<P> v;
	vector<P> tri;
	REP(i,111111){
		if(je[i].size() == 0)continue;
		sort(ALL(je[i]),greater<double>());
		v.EB((je[i][0] + je[i][1]) / 2.,i);
		v.EB((je[i][0] + je[i][1]) / 2.,i);
		for(int j = 2;j < je[i].size();j++){
			v.EB(je[i][j], i);
		}
		if(je[i].size() >= 3){
			tri.EB(je[i][0] + je[i][1] + je[i][2],i);
		}
	}
	
	
	sort(ALL(v),greater<P>());
	sort(ALL(tri),greater<P>());
	
	//REP(i,n)cout << "v " << v[i].FI << " " << v[i].SE << endl;
	
	vector<double> A;//二個まで
	vector<double> B;//それ以降
	double score = 0;
	int pla = 0;
	priority_queue<P> pq;
	if(tri.size())dp[3] = tri[0].FI;
	REP(i,v.size()){
		double now = v[i].FI;
		int id = v[i].SE;
		if(used[id] <= 1){
			A.PB(now);
		}
		else {
			B.PB(now);
		}
		used[id]++;
		
		if(used[id] == 2){
			//cout << "id is 2 :" << je[id].size() << endl;
			for(int j = 2;j < je[id].size();j++){
				pq.push(MP(je[id][j],id));
			}
			mp[id] = 2;
		}
		score += now;
		
		while(pla < tri.size() && used[tri[pla].SE] > 0)pla++;
		while(!pq.empty() && mp[pq.top().SE] < used[pq.top().SE]){
			mp[pq.top().SE]++;
			pq.pop();
		}
		
		if(used[id] == 1){
			if(B.size()){
			//	cout << "mel " << (ll)(score + v[i+1].FI - B.back()) << endl;
				dp[i + 1] = max(dp[i + 1], (ll)(score + v[i+1].FI - B.back()));
			}
		}
		else {
			dp[i + 1] = max(dp[i + 1], (ll)(score));
			if(pla < tri.size()){
				//cout << "!!!!!! " << (ll)(score + tri[pla].FI) << endl;
				dp[i + 4] = max(dp[i + 4], (ll)(score + tri[pla].FI));
			}
			if(!pq.empty()){
				//cout << "!!!! " << (ll)(score + pq.top().FI) << endl;
				dp[i + 2] = max(dp[i + 2], (ll)(score + pq.top().FI));
			}
			if(pla < tri.size() && !pq.empty()){
				//cout << "!!" << (ll)(score + pq.top().FI + tri[pla].FI) << endl;
				dp[i + 5] = max(dp[i + 5], (ll)(score + pq.top().FI + tri[pla].FI));
			}
		}
		//cout << "i " << i << " vFI " << v[i].FI << " vSE " << v[i].SE << " score " << score << " B " << B.size() << " pq " << pq.size() << endl;
		
	}
	
	REP(i,n)cout << dp[i+1] << endl;
	
	return 0;
}

```