#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;
}

Measured memory_bytes: 23024