#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int n,k,vis[N];
vector<ll>v[N];
multiset<ll>one,three;
vector<pair<ll,int> >jewels;
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        int x,y;scanf("%d%d",&x,&y);
        v[x].emplace_back(y*2);
    }
    for(int i=1;i<=k;i++)
    {
        sort(v[i].begin(),v[i].end(),greater<int>());
        if(v[i].size()>2) three.insert(v[i][0]+v[i][1]+v[i][2]);
        ll avg=v[i][0]+v[i][1]>>1;
        jewels.push_back({avg,i});
        jewels.push_back({avg,i});
        for(int j=2;j<v[i].size();j++)
        jewels.push_back({v[i][j],i});
    }
    sort(jewels.begin(),jewels.end(),greater<pair<ll,int>>());
    ll sum=0,mnone=1ll<<60,mntwo=1ll<<60;
    for(int i=0;i<n;i++)
    {
        ll ans=-2,value=jewels[i].first,c=jewels[i].second;
        if(vis[c]==0)
        {
            if(!one.empty())
                ans=max(ans,sum+*one.rbegin());
            ans=max(ans,sum-mnone+value+jewels[i+1].first);
            if(!three.empty())
                ans=max(ans,sum-mntwo+*three.rbegin());
            if(v[c].size()>2)
                three.erase(three.find(v[c][0]+v[c][1]+v[c][2]));
        }
        else
        {
            ans=sum+value;
            if(vis[c]==1)
            {
                for(int j=2;j<v[c].size();j++)
                    one.insert(v[c][j]);
                mntwo=min(mntwo,v[c][0]+v[c][1]);
            }
            else
            {
                one.erase(one.find(value));
                mnone=min(mnone,value);
            }
        }
        vis[c]++;
        sum+=value;
        printf("%lld\n",ans/2);
    }
}

### Prompt

Generate 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<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int n,k,vis[N];
vector<ll>v[N];
multiset<ll>one,three;
vector<pair<ll,int> >jewels;
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        int x,y;scanf("%d%d",&x,&y);
        v[x].emplace_back(y*2);
    }
    for(int i=1;i<=k;i++)
    {
        sort(v[i].begin(),v[i].end(),greater<int>());
        if(v[i].size()>2) three.insert(v[i][0]+v[i][1]+v[i][2]);
        ll avg=v[i][0]+v[i][1]>>1;
        jewels.push_back({avg,i});
        jewels.push_back({avg,i});
        for(int j=2;j<v[i].size();j++)
        jewels.push_back({v[i][j],i});
    }
    sort(jewels.begin(),jewels.end(),greater<pair<ll,int>>());
    ll sum=0,mnone=1ll<<60,mntwo=1ll<<60;
    for(int i=0;i<n;i++)
    {
        ll ans=-2,value=jewels[i].first,c=jewels[i].second;
        if(vis[c]==0)
        {
            if(!one.empty())
                ans=max(ans,sum+*one.rbegin());
            ans=max(ans,sum-mnone+value+jewels[i+1].first);
            if(!three.empty())
                ans=max(ans,sum-mntwo+*three.rbegin());
            if(v[c].size()>2)
                three.erase(three.find(v[c][0]+v[c][1]+v[c][2]));
        }
        else
        {
            ans=sum+value;
            if(vis[c]==1)
            {
                for(int j=2;j<v[c].size();j++)
                    one.insert(v[c][j]);
                mntwo=min(mntwo,v[c][0]+v[c][1]);
            }
            else
            {
                one.erase(one.find(value));
                mnone=min(mnone,value);
            }
        }
        vis[c]++;
        sum+=value;
        printf("%lld\n",ans/2);
    }
}

```