#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define poly vector<ll>
#define sqr(x) ((x)*(x))
#define mp make_pair
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline ll read(){
	ll x = 0; char ch = gc(); bool positive = 1;
	for (; !isdigit(ch); ch = gc())	if (ch == '-')	positive = 0;
	for (; isdigit(ch); ch = gc())	x = x * 10 + ch - '0';
	return positive ? x : -x;
}
inline void write(ll a){
    if(a<0){
    	a=-a; putchar('-');
	}
    if(a>=10)write(a/10);
    putchar('0'+a%10);
}
inline void wri(ll a){write(a); putchar(' ');}
inline void writeln(ll a){write(a); puts("");}
const int N=200005;
const ll inf=1e18;
vector<int> v[N];
poly me(poly a,poly b){
	int n=a.size(),m=b.size(),i=0,j=0;
	poly c(n+m-1);
	while(i<n&&j<m){
		c[i+j]=a[i]+b[j];
		if((i+1<n&&(j+1==m||a[i+1]+b[j]>a[i]+b[j+1])))i++; else j++;
	}
	return c;
}
poly operator +(poly a,poly b){
	poly A[2],B[2];
	for(int i=0;i<2;i++){
		for(unsigned j=i;j<a.size();j+=2)A[i].push_back(a[j]);
		for(unsigned j=i;j<b.size();j+=2)B[i].push_back(b[j]);
	}
	poly ans(a.size()+b.size()-1);
	for(auto &i:ans)i=-inf;
	for(int i=0;i<2;i++){
		for(int j=0;j<2;j++){
			poly c=me(A[i],B[j]);
			for(unsigned k=0;k<c.size();k++){ ans[k*2+i+j]=max(ans[k*2+i+j],c[k]); }
		}
	}
	return ans;
}
poly solve(int l,int r){
	if(l==r){
		sort(v[l].begin(),v[l].end()); 
		int m=v[l].size(); poly ans(m+1);
		for(int i=1;i<=m;i++)ans[i]=ans[i-1]+v[l][m-i];
		ans[1]=-inf; //cout<<l<<" fjzzq "<<ans.size()<<endl;
		return ans;
	}
	int mid=(l+r)>>1;
	return solve(l,mid)+solve(mid+1,r);
}
signed main(){
	int n=read(),k=read();
	for(int i=1;i<=n;i++){
		int c=read(),w=read();
		v[c].push_back(w);
	}
	poly ans(n+1);
	for(auto &i:ans)i=-inf;
	for(int i=1;i<=3;i++){
		for(int i=1;i<=k;i++)swap(v[i],v[((ll)rand()<<15^rand())%i+1]);
		poly zs=solve(1,k);
		for(int i=1;i<=n;i++)ans[i]=max(ans[i],zs[i]);
	}
	for(int i=1;i<=n;i++){
		if(ans[i]<0)puts("-1");
		else writeln(ans[i]);
	}
}

### Prompt

Develop a solution in CPP 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;
typedef long long ll;
#define poly vector<ll>
#define sqr(x) ((x)*(x))
#define mp make_pair
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline ll read(){
	ll x = 0; char ch = gc(); bool positive = 1;
	for (; !isdigit(ch); ch = gc())	if (ch == '-')	positive = 0;
	for (; isdigit(ch); ch = gc())	x = x * 10 + ch - '0';
	return positive ? x : -x;
}
inline void write(ll a){
    if(a<0){
    	a=-a; putchar('-');
	}
    if(a>=10)write(a/10);
    putchar('0'+a%10);
}
inline void wri(ll a){write(a); putchar(' ');}
inline void writeln(ll a){write(a); puts("");}
const int N=200005;
const ll inf=1e18;
vector<int> v[N];
poly me(poly a,poly b){
	int n=a.size(),m=b.size(),i=0,j=0;
	poly c(n+m-1);
	while(i<n&&j<m){
		c[i+j]=a[i]+b[j];
		if((i+1<n&&(j+1==m||a[i+1]+b[j]>a[i]+b[j+1])))i++; else j++;
	}
	return c;
}
poly operator +(poly a,poly b){
	poly A[2],B[2];
	for(int i=0;i<2;i++){
		for(unsigned j=i;j<a.size();j+=2)A[i].push_back(a[j]);
		for(unsigned j=i;j<b.size();j+=2)B[i].push_back(b[j]);
	}
	poly ans(a.size()+b.size()-1);
	for(auto &i:ans)i=-inf;
	for(int i=0;i<2;i++){
		for(int j=0;j<2;j++){
			poly c=me(A[i],B[j]);
			for(unsigned k=0;k<c.size();k++){ ans[k*2+i+j]=max(ans[k*2+i+j],c[k]); }
		}
	}
	return ans;
}
poly solve(int l,int r){
	if(l==r){
		sort(v[l].begin(),v[l].end()); 
		int m=v[l].size(); poly ans(m+1);
		for(int i=1;i<=m;i++)ans[i]=ans[i-1]+v[l][m-i];
		ans[1]=-inf; //cout<<l<<" fjzzq "<<ans.size()<<endl;
		return ans;
	}
	int mid=(l+r)>>1;
	return solve(l,mid)+solve(mid+1,r);
}
signed main(){
	int n=read(),k=read();
	for(int i=1;i<=n;i++){
		int c=read(),w=read();
		v[c].push_back(w);
	}
	poly ans(n+1);
	for(auto &i:ans)i=-inf;
	for(int i=1;i<=3;i++){
		for(int i=1;i<=k;i++)swap(v[i],v[((ll)rand()<<15^rand())%i+1]);
		poly zs=solve(1,k);
		for(int i=1;i<=n;i++)ans[i]=max(ans[i],zs[i]);
	}
	for(int i=1;i<=n;i++){
		if(ans[i]<0)puts("-1");
		else writeln(ans[i]);
	}
}

```