#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
#include<assert.h>
#include<chrono>
#include<random>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
#define SZ(x) ((int)x.size())
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
inline LL read()
{
	LL f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int stack[20];
template<typename T>inline void write(T x)
{
	if(x<0){putchar('-');x=-x;}
    if(!x){putchar('0');return;}
    int top=0;
    while(x)stack[++top]=x%10,x/=10;
    while(top)putchar(stack[top--]+'0');
}
template<typename T>inline void pr1(T x){write(x);putchar(' ');}
template<typename T>inline void pr2(T x){write(x);putchar('\n');}
template<typename T>inline void chkmin(T &x,T y){x=x<y?x:y;}
template<typename T>inline void chkmax(T &x,T y){x=x>y?x:y;}
const int MAXN=200005;
struct node
{
	LL C;int pos,id;
	node(){}node(LL _C,int _pos,int _id){C=_C;pos=_pos;id=_id;}
};
bool cmp(node n1,node n2){return n1.C==n2.C?n1.pos==n2.pos?n1.id<n2.id:n1.pos<n2.pos:n1.C>n2.C;}
vector<node> CH;
multiset<LL> se[4];
multiset<LL>::iterator it;
int vis[MAXN],cnt;
int n,K,C[MAXN],V[MAXN];
vector<LL> vec[MAXN];
/*
0 已经合法 没选的max 
1 已经合法 删去1个后仍然合法的min
2 已经合法且只有2个的min
3 没有选中的3个的max 
*/	
void maintain(node T)
{
	if(vis[T.pos]==1)
	{
		if(SZ(vec[T.pos])<=2)return ;
		it=se[3].find(vec[T.pos][0]+vec[T.pos][1]+vec[T.pos][2]);
		se[3].erase(it);
	}
	else if(vis[T.pos]==2)
	{
		if(SZ(vec[T.pos])>2)se[0].insert(vec[T.pos][2]);
		se[2].insert(vec[T.pos][0]+vec[T.pos][1]);
	}
	else
	{
		se[0].erase(it=se[0].find(T.C));
		if(T.id+1<SZ(vec[T.pos]))se[0].insert(vec[T.pos][T.id+1]);
		
		if(vis[T.pos]==3)se[1].insert(T.C);
		else se[1].erase(it=se[1].find(vec[T.pos][T.id-1])),se[1].insert(T.C);
		
		if(vis[T.pos]==3)se[2].erase(it=se[2].find(vec[T.pos][0]+vec[T.pos][1]));
	}
}
int main()
{
//	freopen("f.in","r",stdin);
//	freopen("f.out","w",stdout);
	n=read();K=read();
	for(int i=1;i<=n;i++)
	{
		int c=read(),v=read();
		vec[c].emplace_back(v);
	}
	for(int i=1;i<=K;i++)sort(vec[i].begin(),vec[i].end()),reverse(vec[i].begin(),vec[i].end());
	for(int i=1;i<=K;i++)
	{
		assert(SZ(vec[i])>=2);
		vec[i][0]=vec[i][1]=vec[i][0]+vec[i][1];
		for(int j=2;j<SZ(vec[i]);j++)vec[i][j]=2*vec[i][j];
		for(int j=0;j<SZ(vec[i]);j++)CH.emplace_back(node(vec[i][j],i,j));
	}sort(CH.begin(),CH.end(),cmp);
	for(int i=1;i<=K;i++)if(SZ(vec[i])>=3)
		se[3].insert(vec[i][0]+vec[i][1]+vec[i][2]);
	LL sum=0;
	for(int i=1;i<=n;i++)
	{
		node temp=CH[i-1];sum+=temp.C;
		++vis[temp.pos];
		if(vis[temp.pos]==1)++cnt;
		if(vis[temp.pos]==2)--cnt;
		maintain(temp);
		if(!cnt)pr2(sum>>1);
		else
		{
			LL ans=-1e18;
			/*
			0 已经合法 没选的max 
			1 已经合法 删去1个后仍然合法的min
			2 已经合法且只有2个的min
			3 没有选中的3个的max 
			*/	
			if(SZ(se[0]))
			{
				it=se[0].end();--it;
				chkmax(ans,sum-temp.C+*it);
			}
			if(SZ(se[1]))
			{
				it=se[1].begin();
				chkmax(ans,sum+temp.C-*it);
			}
			if(SZ(se[2]))
			{
				it=se[2].begin();LL val=*it;
				if(SZ(vec[temp.pos])>=3)chkmax(ans,sum+temp.C+vec[temp.pos][2]-val);
				if(SZ(se[3]))
				{
					it=se[3].end();--it;
					chkmax(ans,sum-temp.C-val+*it);
				}
			}
			if(ans<=0)pr2(-1);
			else pr2(ans>>1);
		}
	}
	return 0;
}


### Prompt

Please formulate a Cpp solution 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<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
#include<assert.h>
#include<chrono>
#include<random>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
#define SZ(x) ((int)x.size())
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
inline LL read()
{
	LL f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int stack[20];
template<typename T>inline void write(T x)
{
	if(x<0){putchar('-');x=-x;}
    if(!x){putchar('0');return;}
    int top=0;
    while(x)stack[++top]=x%10,x/=10;
    while(top)putchar(stack[top--]+'0');
}
template<typename T>inline void pr1(T x){write(x);putchar(' ');}
template<typename T>inline void pr2(T x){write(x);putchar('\n');}
template<typename T>inline void chkmin(T &x,T y){x=x<y?x:y;}
template<typename T>inline void chkmax(T &x,T y){x=x>y?x:y;}
const int MAXN=200005;
struct node
{
	LL C;int pos,id;
	node(){}node(LL _C,int _pos,int _id){C=_C;pos=_pos;id=_id;}
};
bool cmp(node n1,node n2){return n1.C==n2.C?n1.pos==n2.pos?n1.id<n2.id:n1.pos<n2.pos:n1.C>n2.C;}
vector<node> CH;
multiset<LL> se[4];
multiset<LL>::iterator it;
int vis[MAXN],cnt;
int n,K,C[MAXN],V[MAXN];
vector<LL> vec[MAXN];
/*
0 已经合法 没选的max 
1 已经合法 删去1个后仍然合法的min
2 已经合法且只有2个的min
3 没有选中的3个的max 
*/	
void maintain(node T)
{
	if(vis[T.pos]==1)
	{
		if(SZ(vec[T.pos])<=2)return ;
		it=se[3].find(vec[T.pos][0]+vec[T.pos][1]+vec[T.pos][2]);
		se[3].erase(it);
	}
	else if(vis[T.pos]==2)
	{
		if(SZ(vec[T.pos])>2)se[0].insert(vec[T.pos][2]);
		se[2].insert(vec[T.pos][0]+vec[T.pos][1]);
	}
	else
	{
		se[0].erase(it=se[0].find(T.C));
		if(T.id+1<SZ(vec[T.pos]))se[0].insert(vec[T.pos][T.id+1]);
		
		if(vis[T.pos]==3)se[1].insert(T.C);
		else se[1].erase(it=se[1].find(vec[T.pos][T.id-1])),se[1].insert(T.C);
		
		if(vis[T.pos]==3)se[2].erase(it=se[2].find(vec[T.pos][0]+vec[T.pos][1]));
	}
}
int main()
{
//	freopen("f.in","r",stdin);
//	freopen("f.out","w",stdout);
	n=read();K=read();
	for(int i=1;i<=n;i++)
	{
		int c=read(),v=read();
		vec[c].emplace_back(v);
	}
	for(int i=1;i<=K;i++)sort(vec[i].begin(),vec[i].end()),reverse(vec[i].begin(),vec[i].end());
	for(int i=1;i<=K;i++)
	{
		assert(SZ(vec[i])>=2);
		vec[i][0]=vec[i][1]=vec[i][0]+vec[i][1];
		for(int j=2;j<SZ(vec[i]);j++)vec[i][j]=2*vec[i][j];
		for(int j=0;j<SZ(vec[i]);j++)CH.emplace_back(node(vec[i][j],i,j));
	}sort(CH.begin(),CH.end(),cmp);
	for(int i=1;i<=K;i++)if(SZ(vec[i])>=3)
		se[3].insert(vec[i][0]+vec[i][1]+vec[i][2]);
	LL sum=0;
	for(int i=1;i<=n;i++)
	{
		node temp=CH[i-1];sum+=temp.C;
		++vis[temp.pos];
		if(vis[temp.pos]==1)++cnt;
		if(vis[temp.pos]==2)--cnt;
		maintain(temp);
		if(!cnt)pr2(sum>>1);
		else
		{
			LL ans=-1e18;
			/*
			0 已经合法 没选的max 
			1 已经合法 删去1个后仍然合法的min
			2 已经合法且只有2个的min
			3 没有选中的3个的max 
			*/	
			if(SZ(se[0]))
			{
				it=se[0].end();--it;
				chkmax(ans,sum-temp.C+*it);
			}
			if(SZ(se[1]))
			{
				it=se[1].begin();
				chkmax(ans,sum+temp.C-*it);
			}
			if(SZ(se[2]))
			{
				it=se[2].begin();LL val=*it;
				if(SZ(vec[temp.pos])>=3)chkmax(ans,sum+temp.C+vec[temp.pos][2]-val);
				if(SZ(se[3]))
				{
					it=se[3].end();--it;
					chkmax(ans,sum-temp.C-val+*it);
				}
			}
			if(ans<=0)pr2(-1);
			else pr2(ans>>1);
		}
	}
	return 0;
}


```