#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define REP(i,n) for(int i=0;i<(n);i++)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;

template<class T> inline void read(T &x){
	int f=0;x=0;char ch=getchar();
	for(;!isdigit(ch);ch=getchar())f|=(ch=='-');
	for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';
	if(f)x=-x;
}

const int N=500005;
struct node{
	ll v; int k,c;
	friend bool operator < (node a,node b){
		return a.v>b.v||a.v==b.v&&a.k>b.k;
	}
} x[N];
int nxt[N],las[N],n,K,m,a,b,cnt;
ll ans[N],sum;
vi w[N];

set<pair<ll,int> > sig,dou,tri;
ll s1,s2;

int main(){
	read(n),read(K);
	rep(i,1,n){
		read(a),read(b);
		w[a].pb(b*2);
	}
	rep(i,1,K){
		sort(w[i].begin(),w[i].end(),greater<int>());
		x[++m]=(node){((ll)w[i][0]+w[i][1])/2,2,i};
		for(int k=2;k<w[i].size();k++) x[++m]=(node){w[i][k],1,i};
	}
	sort(x+1,x+m+1);
	per(i,m,1) nxt[i]=las[x[i].c],las[x[i].c]=i;
	//rep(i,1,m) cout<<i<<" "<<x[i].v<<" "<<x[i].k<<" "<<x[i].c<<endl;
	rep(i,1,K){
		dou.insert(mp((ll)w[i][0]+w[i][1],i));
		if(w[i].size()>2) tri.insert(mp((ll)w[i][0]+w[i][1]+w[i][2],i));
	}
	rep(i,1,m){
		if(x[i].k==2){
			if(!sig.empty()){
				ans[cnt+1]=max(ans[cnt+1],sum+sig.rbegin()->fi);
			}
			if(s1&&!dou.empty()){
				ans[cnt+1]=max(ans[cnt+1],sum+dou.rbegin()->fi-s1);
			}
			if(s2&&!tri.empty()){
				ans[cnt+1]=max(ans[cnt+1],sum+tri.rbegin()->fi-s2);
			}
		}
		cnt+=x[i].k;
		sum+=x[i].v*x[i].k;
		ans[cnt]=sum;
		if(x[i].k==2){
			s2=x[i].v*2;
			if(nxt[i]){
				sig.insert(mp(x[nxt[i]].v,x[i].c));
				tri.erase(mp(x[i].v*2+x[nxt[i]].v,x[i].c));
			}
			dou.erase(mp(x[i].v*2,x[i].c));
		}
		else{
			s1=x[i].v;
			sig.erase(mp(x[i].v,x[i].c));
			if(nxt[i]) sig.insert(mp(x[nxt[i]].v,x[i].c));
		}
	}
	rep(i,1,n) printf("%lld\n",!ans[i]?-1:ans[i]/2);
	return 0;
}
### 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>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define REP(i,n) for(int i=0;i<(n);i++)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;

template<class T> inline void read(T &x){
	int f=0;x=0;char ch=getchar();
	for(;!isdigit(ch);ch=getchar())f|=(ch=='-');
	for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';
	if(f)x=-x;
}

const int N=500005;
struct node{
	ll v; int k,c;
	friend bool operator < (node a,node b){
		return a.v>b.v||a.v==b.v&&a.k>b.k;
	}
} x[N];
int nxt[N],las[N],n,K,m,a,b,cnt;
ll ans[N],sum;
vi w[N];

set<pair<ll,int> > sig,dou,tri;
ll s1,s2;

int main(){
	read(n),read(K);
	rep(i,1,n){
		read(a),read(b);
		w[a].pb(b*2);
	}
	rep(i,1,K){
		sort(w[i].begin(),w[i].end(),greater<int>());
		x[++m]=(node){((ll)w[i][0]+w[i][1])/2,2,i};
		for(int k=2;k<w[i].size();k++) x[++m]=(node){w[i][k],1,i};
	}
	sort(x+1,x+m+1);
	per(i,m,1) nxt[i]=las[x[i].c],las[x[i].c]=i;
	//rep(i,1,m) cout<<i<<" "<<x[i].v<<" "<<x[i].k<<" "<<x[i].c<<endl;
	rep(i,1,K){
		dou.insert(mp((ll)w[i][0]+w[i][1],i));
		if(w[i].size()>2) tri.insert(mp((ll)w[i][0]+w[i][1]+w[i][2],i));
	}
	rep(i,1,m){
		if(x[i].k==2){
			if(!sig.empty()){
				ans[cnt+1]=max(ans[cnt+1],sum+sig.rbegin()->fi);
			}
			if(s1&&!dou.empty()){
				ans[cnt+1]=max(ans[cnt+1],sum+dou.rbegin()->fi-s1);
			}
			if(s2&&!tri.empty()){
				ans[cnt+1]=max(ans[cnt+1],sum+tri.rbegin()->fi-s2);
			}
		}
		cnt+=x[i].k;
		sum+=x[i].v*x[i].k;
		ans[cnt]=sum;
		if(x[i].k==2){
			s2=x[i].v*2;
			if(nxt[i]){
				sig.insert(mp(x[nxt[i]].v,x[i].c));
				tri.erase(mp(x[i].v*2+x[nxt[i]].v,x[i].c));
			}
			dou.erase(mp(x[i].v*2,x[i].c));
		}
		else{
			s1=x[i].v;
			sig.erase(mp(x[i].v,x[i].c));
			if(nxt[i]) sig.insert(mp(x[nxt[i]].v,x[i].c));
		}
	}
	rep(i,1,n) printf("%lld\n",!ans[i]?-1:ans[i]/2);
	return 0;
}
```