// includes {{{
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<tuple>
#include<cmath>
#include<random>
#include<cassert>
// #include<deque>
// #include<multiset>
// #include<bitset>
// #include<cstring>
// #include<bits/stdc++.h>
// }}}
using namespace std;
using ll = long long;

int n, k;
const int N = 2e5 + 10;
int c[N], a[N];
vector<int> v[N];

// smin, smax {{{
// clang-format off
template < class T, class U > inline void smin(T &a, const U &b) { a = a < (T) b ? a : b; }
template < class T, class U > inline void smax(T &a, const U &b) { a = a < (T) b ? b : a; }
// clang-format on
// }}}


int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  cin >> n >> k;
  for(int i = 0; i < n; i++) {
    cin >> c[i] >> a[i];
    v[c[i]].emplace_back(a[i]);
  }
  
  using P = tuple<ll, int, int, int, int>;
  vector<P> w;
  using Q = tuple<ll, int>;
  set<Q> bestAdd1;
  set<Q> bestAdd3;
  set<Q> bestDel1;
  set<Q> bestDel2;
  for(int i = 1; i <= k; i++) if(v[i].size()) {
    sort(rbegin(v[i]), rend(v[i]));
    w.emplace_back(v[i][0] + v[i][1], 2, i, 0, 2);
    for(int j = 2; j < (int) v[i].size(); j++) {
      w.emplace_back(v[i][j] * 2, 1, i, -j, j + 1);
    }
    // !!!!!!!!! 同じ値同じインデックスのタイがうまくとれていない !!!!!!!!!!!!!!!
    // 教訓 : タイはタプルとかに予めしておいて必ずとろう
    if(v[i].size() >= 3) bestAdd3.insert(Q((ll) v[i][0] + v[i][1] + v[i][2], i));
    /// overflowwwwww!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
  }
  sort(begin(w), end(w));
  int now = 0;
  ll x = 0;
  for(int i = 1; i <= n; i++) {
    ll val;
    ll res = -1;
    int weight, index, next;
    assert(w.size());
    tie(val, weight, index, ignore, next) = w.back();
    val = val * weight / 2;
    if(now + weight > i) {
      assert(weight == 2);
      if(bestAdd1.size()) {
        smax(res, x + get<0>(*--bestAdd1.end()));
      }
      if(bestAdd3.size() && bestDel2.size()) {
        smax(res, x + get<0>(*--bestAdd3.end()) - get<0>(*bestDel2.begin()));
      }
      if(bestDel1.size()) {
        smax(res, x + val - get<0>(*bestDel1.begin()));
      }
    } else {
      // 同時に起こり得るものはinsertを後に
      now += weight;
      x += val;
      if(next - 1 >= 2) {
        size_t sz = bestAdd1.size();
        bestAdd1.erase(Q(v[index][next-1], index));
        assert(sz != bestAdd1.size());
      }
      if(next - 1 == 1) {
        bestDel2.insert(Q(v[index][0] + v[index][1], index));
        if(v[index].size() >= 3) bestAdd3.erase(Q((ll) v[index][0] + v[index][1] + v[index][2], index));
        // here too
      }
      if(next - 1 == 2) {
        bestDel2.erase(Q(v[index][0] + v[index][1], index));
      }
      if(next - 1 >= 3) {
        bestDel1.erase(Q(v[index][next - 2], index));
      }
      if(next - 1 >= 2) {
        bestDel1.insert(Q(v[index][next - 1], index));
      }
      if(next < (int) v[index].size()) bestAdd1.insert(Q(v[index][next], index));

      w.pop_back();
      res = x;
    }
    cout << res << "\n";
  }
  assert(bestAdd1.size() == 0);
  return 0;
}



Measured memory_bytes: 22804