#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
int n,k;
vector<int>vec[100005];
vector<int>numm;
bool cmp(const int &a,const int &b){
	return vec[a][0]+vec[a][1] > vec[b][0]+vec[b][1];
}
//x,dp[x],何種類
vector<pair<int,pair<ll,int> > >num[(1<<18)][2];
int rec(int k,int L,int R){
	if(L == R){
		ll sum = 0;
		num[k][0].pb(mp(0,mp(0,0)));
		for(int i=0;i<vec[numm[L]].size();i++){
			sum += vec[numm[L]][i];
			if(i >= 1){
				num[k][1-i%2].pb(mp(i+1,mp(sum,1)));
			}
		}
		return vec[numm[L]].size();
	}
	int mx = 0;
	mx += rec(k*2+1,L,(L+R)/2);
	mx += rec(k*2+2,(L+R)/2+1,R);
	vector<pair<ll,int> >tmp;
	tmp.resize(mx+5,mp(-1e18,0));
	for(int par1=0;par1<2;par1++){
		for(int par2=0;par2<2;par2++){
			//num[k*2+1][par1] & num[k*2+2][par2]
		//	cout<<num[k*2+1][par1].size()<<" "<<num[k*2+2][par2].size()<<endl;
			if(num[k*2+1][par1].size() == 0 || num[k*2+2][par2].size() == 0) continue;
			//マージする
			int cur = 0;
			for(int i=0;i+1<num[k*2+1][par1].size()+num[k*2+2][par2].size();i++){
				//num[k*2+1][par1][cur].sc.fi+num[k*2+2][par2][i-cur].sc.fi < num[k*2+1][par1][cur+1].sc.fi+num[k*2+2][par2][i-cur-1].sc.fi ?
				if(i-cur == num[k*2+2][par2].size()) cur++;
				while(cur < i && cur+1 < num[k*2+1][par1].size() && num[k*2+1][par1][cur].sc.fi+num[k*2+2][par2][i-cur].sc.fi < num[k*2+1][par1][cur+1].sc.fi+num[k*2+2][par2][i-cur-1].sc.fi) cur++;
				//正しいcur
				int X = num[k*2+1][par1][cur].fi + num[k*2+2][par2][i-cur].fi;
				ll DP = num[k*2+1][par1][cur].sc.fi + num[k*2+2][par2][i-cur].sc.fi;
				int ty = num[k*2+1][par1][cur].sc.sc + num[k*2+2][par2][i-cur].sc.sc;
				tmp[X] = max(tmp[X],mp(DP,ty));
			}
		}
	}
	for(int i=0;i<mx+5;i++){
		if(tmp[i].fi < -1e17) continue;
		num[k][i%2].pb(mp(i,tmp[i]));
		//cout<<L<<" "<<R<<" "<<i<<" "<<tmp[i].fi<<" "<<tmp[i].sc<<endl;
	}
	return mx;
}
ll dp[200005];
int ty[200005];
ll mx[100005];
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++){
		int c,v; scanf("%d%d",&c,&v);
		vec[c].pb(v);
	}
	for(int i=1;i<=k;i++){
		numm.pb(i);
		sort(vec[i].begin(),vec[i].end(),greater<int>());
	}
	sort(numm.begin(),numm.end(),cmp);
	mx[k] = -1e18;
	for(int i=k-1;i>=0;i--){
		ll sum = -1e18;
		if(vec[numm[i]].size() >= 3){
			ll S = 0;
			rep(j,3) S += vec[numm[i]][j];
			sum = S;
		}
		mx[i] = max(mx[i+1],sum);
	}
	//一旦上位2つのsumが大きいものから連続して取るパターンのみ考える
	//偶奇に分けて分割統治して、凸関数同士のマージをする、この時に上から何種類取ったかも覚えておく
	//最後に、そうして出てきたdp[x]について dp[x+3] = max(dp[x+3],dp[x]+func(x))をする
	//func(x)はdp[x]で取っていない色のうち、上位3つの和の最大値
	//で、できる気がする
	rec(0,0,k-1);
	for(int i=0;i<200005;i++) dp[i] = -1e18;
	rep(q,2){
		for(int i=0;i<num[0][q].size();i++){
			if(dp[num[0][q][i].fi] < num[0][q][i].sc.fi){
				dp[num[0][q][i].fi] = num[0][q][i].sc.fi;
				ty[num[0][q][i].fi] = num[0][q][i].sc.sc;
			}
		}
	}
	//for(int i=0;i<=n;i++) cout<<dp[i]<<" "<<ty[i]<<endl;
	for(int i=0;i<=n-3;i++){
		dp[i+3] = max(dp[i+3],dp[i]+mx[ty[i]]);
	}
	for(int i=1;i<=n;i++){
		if(dp[i] >= 0) printf("%lld\n",dp[i]);
		else puts("-1");
	}
}
### Prompt

Construct a CPP code solution to the problem outlined:

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;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
int n,k;
vector<int>vec[100005];
vector<int>numm;
bool cmp(const int &a,const int &b){
	return vec[a][0]+vec[a][1] > vec[b][0]+vec[b][1];
}
//x,dp[x],何種類
vector<pair<int,pair<ll,int> > >num[(1<<18)][2];
int rec(int k,int L,int R){
	if(L == R){
		ll sum = 0;
		num[k][0].pb(mp(0,mp(0,0)));
		for(int i=0;i<vec[numm[L]].size();i++){
			sum += vec[numm[L]][i];
			if(i >= 1){
				num[k][1-i%2].pb(mp(i+1,mp(sum,1)));
			}
		}
		return vec[numm[L]].size();
	}
	int mx = 0;
	mx += rec(k*2+1,L,(L+R)/2);
	mx += rec(k*2+2,(L+R)/2+1,R);
	vector<pair<ll,int> >tmp;
	tmp.resize(mx+5,mp(-1e18,0));
	for(int par1=0;par1<2;par1++){
		for(int par2=0;par2<2;par2++){
			//num[k*2+1][par1] & num[k*2+2][par2]
		//	cout<<num[k*2+1][par1].size()<<" "<<num[k*2+2][par2].size()<<endl;
			if(num[k*2+1][par1].size() == 0 || num[k*2+2][par2].size() == 0) continue;
			//マージする
			int cur = 0;
			for(int i=0;i+1<num[k*2+1][par1].size()+num[k*2+2][par2].size();i++){
				//num[k*2+1][par1][cur].sc.fi+num[k*2+2][par2][i-cur].sc.fi < num[k*2+1][par1][cur+1].sc.fi+num[k*2+2][par2][i-cur-1].sc.fi ?
				if(i-cur == num[k*2+2][par2].size()) cur++;
				while(cur < i && cur+1 < num[k*2+1][par1].size() && num[k*2+1][par1][cur].sc.fi+num[k*2+2][par2][i-cur].sc.fi < num[k*2+1][par1][cur+1].sc.fi+num[k*2+2][par2][i-cur-1].sc.fi) cur++;
				//正しいcur
				int X = num[k*2+1][par1][cur].fi + num[k*2+2][par2][i-cur].fi;
				ll DP = num[k*2+1][par1][cur].sc.fi + num[k*2+2][par2][i-cur].sc.fi;
				int ty = num[k*2+1][par1][cur].sc.sc + num[k*2+2][par2][i-cur].sc.sc;
				tmp[X] = max(tmp[X],mp(DP,ty));
			}
		}
	}
	for(int i=0;i<mx+5;i++){
		if(tmp[i].fi < -1e17) continue;
		num[k][i%2].pb(mp(i,tmp[i]));
		//cout<<L<<" "<<R<<" "<<i<<" "<<tmp[i].fi<<" "<<tmp[i].sc<<endl;
	}
	return mx;
}
ll dp[200005];
int ty[200005];
ll mx[100005];
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++){
		int c,v; scanf("%d%d",&c,&v);
		vec[c].pb(v);
	}
	for(int i=1;i<=k;i++){
		numm.pb(i);
		sort(vec[i].begin(),vec[i].end(),greater<int>());
	}
	sort(numm.begin(),numm.end(),cmp);
	mx[k] = -1e18;
	for(int i=k-1;i>=0;i--){
		ll sum = -1e18;
		if(vec[numm[i]].size() >= 3){
			ll S = 0;
			rep(j,3) S += vec[numm[i]][j];
			sum = S;
		}
		mx[i] = max(mx[i+1],sum);
	}
	//一旦上位2つのsumが大きいものから連続して取るパターンのみ考える
	//偶奇に分けて分割統治して、凸関数同士のマージをする、この時に上から何種類取ったかも覚えておく
	//最後に、そうして出てきたdp[x]について dp[x+3] = max(dp[x+3],dp[x]+func(x))をする
	//func(x)はdp[x]で取っていない色のうち、上位3つの和の最大値
	//で、できる気がする
	rec(0,0,k-1);
	for(int i=0;i<200005;i++) dp[i] = -1e18;
	rep(q,2){
		for(int i=0;i<num[0][q].size();i++){
			if(dp[num[0][q][i].fi] < num[0][q][i].sc.fi){
				dp[num[0][q][i].fi] = num[0][q][i].sc.fi;
				ty[num[0][q][i].fi] = num[0][q][i].sc.sc;
			}
		}
	}
	//for(int i=0;i<=n;i++) cout<<dp[i]<<" "<<ty[i]<<endl;
	for(int i=0;i<=n-3;i++){
		dp[i+3] = max(dp[i+3],dp[i]+mx[ty[i]]);
	}
	for(int i=1;i<=n;i++){
		if(dp[i] >= 0) printf("%lld\n",dp[i]);
		else puts("-1");
	}
}
```