#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;
const int N = 2e5 + 10;
int n, k;
vector<int> g[N];
bool bz[N];
struct node
{
    long double x;
    int c;
    bool the_first;
    node(long double X = 0, int C = 0)
    {
        x = X;
        c = C;
        the_first = 0;
    }
}a[N];
priority_queue<pair<long long, pair<int, int> > >no_used_one/*大顶堆*/, used_one /*小顶堆*/, no_used_two/*大顶堆*/, used_two/*小顶堆*/, no_used_three/* 大顶堆*/;
int tag[N];
bool cmp(const node&a, const node&b)
{
    return a.x > b.x || (a.x == b.x && a.c < b.c);
}
int main()
{
    scanf("%d %d", &n, &k);
    for (int i =1 ; i <= n ; i++)
    {
        int c, v;
        scanf("%d %d", &c, &v);
        g[c].push_back(v);
    }
    int tot = 0;
    for (int i = 1 ; i <= k  ; i++)
    {
        sort(g[i].rbegin(), g[i].rend());
        for (int j = 2; j < g[i].size(); j ++)
            a[++tot] = node(g[i][j], i);
        long double v = (long double)(g[i][0] + g[i][1]) / 2;
        a[++tot] = node(v, i);
        a[++tot] = node(v, i);
        no_used_two.push(make_pair(g[i][0] + g[i][1], make_pair(i, 0)));
        if (g[i].size() > 2)
            no_used_three.push(make_pair((long long)g[i][0] + g[i][1] + g[i][2], make_pair(i, 0)));
    }
    sort(a + 1, a + tot + 1, cmp);
    printf("-1\n");
    for (int i = 1; i <= n ; i ++)
        if (!bz[a[i].c])
        {
            bz[a[i].c] = 1;
            a[i].the_first = 1;
        }
    long long all = 0;
    for (int i = 2; i <= n ;i ++)
    {
        if (a[i - 1].the_first)
        {
            all += a[i].x * 2;
            tag[a[i].c] = 2;
            used_two.push(make_pair(-a[i].x * 2, make_pair(a[i].c, 2)));
            if (g[a[i].c].size() > 2)
                no_used_one.push(make_pair(g[a[i].c][2], make_pair(a[i].c, 3)));
            printf("%lld\n", all);
            continue;
        }
        if (!a[i].the_first)
        {
            all += a[i].x;
            tag[a[i].c] ++;
            used_one.push(make_pair(-a[i].x, make_pair(a[i].c, tag[a[i].c])));
            printf("%lld\n", all);
            continue;
        }
        long long ans = -1;
        no_used_one/*大顶堆*/, used_one /*小顶堆*/, no_used_two/*大顶堆*/, used_two/*小顶堆*/, no_used_three/* 大顶堆*/;
        while (!no_used_one.empty() && no_used_one.top().second.second != tag[no_used_one.top().second.first] + 1) {
            pair<int, pair<int, int> > u = no_used_one.top();
            no_used_one.pop();
            if (g[u.second.first].size() >= tag[u.second.first] + 1)
            {
                no_used_one.push(make_pair(g[u.second.first][tag[u.second.first]], make_pair(u.second.first, tag[u.second.first] + 1)));
            }
        }
        if (!no_used_one.empty())
            ans = max(ans, no_used_one.top().first + all);
        while (!no_used_two.empty() && tag[no_used_two.top().second.first])
            no_used_two.pop();
        while (!used_one.empty() && used_one.top().second.second != tag[used_one.top().second.first]) {
            pair<int, pair<int, int> > u = used_one.top();
            used_one.pop();
            used_one.push(make_pair(-g[u.second.first][tag[u.second.first] - 1], make_pair(u.second.first, tag[u.second.first])));
        }
        if (!no_used_two.empty() && !used_one.empty())
            ans = max(ans, all + no_used_two.top().first + used_one.top().first);
        while (!no_used_three.empty() && tag[no_used_three.top().second.first])
            no_used_three.pop();
        while (!used_two.empty() && used_two.top().second.second != tag[used_two.top().second.first])
            used_two.pop();
        if (!no_used_three.empty() && !used_two.empty())
            ans = max(ans, all + no_used_three.top().first + used_two.top().first);
        printf("%lld\n", ans);
    }
    return 0;
}
### Prompt

Please create a solution in cpp 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 <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;
const int N = 2e5 + 10;
int n, k;
vector<int> g[N];
bool bz[N];
struct node
{
    long double x;
    int c;
    bool the_first;
    node(long double X = 0, int C = 0)
    {
        x = X;
        c = C;
        the_first = 0;
    }
}a[N];
priority_queue<pair<long long, pair<int, int> > >no_used_one/*大顶堆*/, used_one /*小顶堆*/, no_used_two/*大顶堆*/, used_two/*小顶堆*/, no_used_three/* 大顶堆*/;
int tag[N];
bool cmp(const node&a, const node&b)
{
    return a.x > b.x || (a.x == b.x && a.c < b.c);
}
int main()
{
    scanf("%d %d", &n, &k);
    for (int i =1 ; i <= n ; i++)
    {
        int c, v;
        scanf("%d %d", &c, &v);
        g[c].push_back(v);
    }
    int tot = 0;
    for (int i = 1 ; i <= k  ; i++)
    {
        sort(g[i].rbegin(), g[i].rend());
        for (int j = 2; j < g[i].size(); j ++)
            a[++tot] = node(g[i][j], i);
        long double v = (long double)(g[i][0] + g[i][1]) / 2;
        a[++tot] = node(v, i);
        a[++tot] = node(v, i);
        no_used_two.push(make_pair(g[i][0] + g[i][1], make_pair(i, 0)));
        if (g[i].size() > 2)
            no_used_three.push(make_pair((long long)g[i][0] + g[i][1] + g[i][2], make_pair(i, 0)));
    }
    sort(a + 1, a + tot + 1, cmp);
    printf("-1\n");
    for (int i = 1; i <= n ; i ++)
        if (!bz[a[i].c])
        {
            bz[a[i].c] = 1;
            a[i].the_first = 1;
        }
    long long all = 0;
    for (int i = 2; i <= n ;i ++)
    {
        if (a[i - 1].the_first)
        {
            all += a[i].x * 2;
            tag[a[i].c] = 2;
            used_two.push(make_pair(-a[i].x * 2, make_pair(a[i].c, 2)));
            if (g[a[i].c].size() > 2)
                no_used_one.push(make_pair(g[a[i].c][2], make_pair(a[i].c, 3)));
            printf("%lld\n", all);
            continue;
        }
        if (!a[i].the_first)
        {
            all += a[i].x;
            tag[a[i].c] ++;
            used_one.push(make_pair(-a[i].x, make_pair(a[i].c, tag[a[i].c])));
            printf("%lld\n", all);
            continue;
        }
        long long ans = -1;
        no_used_one/*大顶堆*/, used_one /*小顶堆*/, no_used_two/*大顶堆*/, used_two/*小顶堆*/, no_used_three/* 大顶堆*/;
        while (!no_used_one.empty() && no_used_one.top().second.second != tag[no_used_one.top().second.first] + 1) {
            pair<int, pair<int, int> > u = no_used_one.top();
            no_used_one.pop();
            if (g[u.second.first].size() >= tag[u.second.first] + 1)
            {
                no_used_one.push(make_pair(g[u.second.first][tag[u.second.first]], make_pair(u.second.first, tag[u.second.first] + 1)));
            }
        }
        if (!no_used_one.empty())
            ans = max(ans, no_used_one.top().first + all);
        while (!no_used_two.empty() && tag[no_used_two.top().second.first])
            no_used_two.pop();
        while (!used_one.empty() && used_one.top().second.second != tag[used_one.top().second.first]) {
            pair<int, pair<int, int> > u = used_one.top();
            used_one.pop();
            used_one.push(make_pair(-g[u.second.first][tag[u.second.first] - 1], make_pair(u.second.first, tag[u.second.first])));
        }
        if (!no_used_two.empty() && !used_one.empty())
            ans = max(ans, all + no_used_two.top().first + used_one.top().first);
        while (!no_used_three.empty() && tag[no_used_three.top().second.first])
            no_used_three.pop();
        while (!used_two.empty() && used_two.top().second.second != tag[used_two.top().second.first])
            used_two.pop();
        if (!no_used_three.empty() && !used_two.empty())
            ans = max(ans, all + no_used_three.top().first + used_two.top().first);
        printf("%lld\n", ans);
    }
    return 0;
}
```