#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
#include <memory>
#include <regex>
using namespace std;

const long long INF = LLONG_MAX / 4;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<long long> > jewel(m);
    for(int i=0; i<n; ++i){
        int col, val;
        cin >> col >> val;
        -- col;
        jewel[col].push_back(val);
    }

    multiset<long long> ms2 = {-INF};
    multiset<long long> ms3 = {-INF};
    vector<pair<long long, int> > v;
    for(int col=0; col<m; ++col){
        sort(jewel[col].rbegin(), jewel[col].rend());
        jewel[col][0] = jewel[col][1] = jewel[col][0] + jewel[col][1];
        for(unsigned i=2; i<jewel[col].size(); ++i)
            jewel[col][i] *= 2;
        for(unsigned i=0; i<jewel[col].size(); ++i)
            v.push_back(make_pair(jewel[col][i], col));
        ms2.insert(jewel[col][0] + jewel[col][1]);
        if(jewel[col].size() >= 3)
            ms3.insert(jewel[col][0] + jewel[col][1] + jewel[col][2]);
    }
    sort(v.rbegin(), v.rend());
    
    multiset<long long> ms1 = {-INF};
    vector<int> cnt(m, 0);
    long long sum = 0;
    long long minVal1 = INF;
    long long minVal2 = INF;
    for(int i=0; i<n; ++i){
        long long val;
        int col;
        tie(val, col) = v[i];

        long long ans = -1;
        if(cnt[col] == 0){
            ans = max(ans, (sum + *ms1.rbegin()) / 2);
            ans = max(ans, (sum - minVal1 + *ms2.rbegin()) / 2);
            ans = max(ans, (sum - minVal2 + *ms3.rbegin()) / 2);

            for(unsigned i=1; i<jewel[col].size(); ++i)
                ms1.insert(jewel[col][i]);
            ms2.erase(ms2.find(jewel[col][0] + jewel[col][1]));
            if(jewel[col].size() >= 3)
                ms3.erase(ms3.find(jewel[col][0] + jewel[col][1] + jewel[col][2]));
        }
        else{
            ans = (sum + val) / 2;
            ms1.erase(ms1.find(val));
            if(cnt[col] == 1)
                minVal2 = min(minVal2, val * 2);
            else
                minVal1 = min(minVal1, val);
        }

        cout << ans << endl;
        ++ cnt[col];
        sum += val;
    }

    return 0;
}
