#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef complex<double> point;
typedef double DOUBLE;
#define xx real()
#define yy imag()

#define REP(i, a, b) for(int i = (a); i < (int)(b); i++)
#define REPN(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define FA(it, x) for(__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
#define SZ(x) (int)(x).size()
#define BE(x) (x).begin(), (x).end()
#define SORT(x) sort(BE(x))
#define _1 first
#define _2 second

#define x1 gray_cat_x1
#define y1 gray_cat_y1

template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define file "I1"

const double EPS = 1e-9;
const double PI = acos(-1.);
const ll INF = 1e17 + 7;
const ll MOD = 1e9 + 7;

const int MAXN = 2e5 + 5;
const int MAXOP = 4;

vi vals[MAXN];
int cur_cnt[MAXN];
set<pair<ll, int> > two_in, three_in, inc_in, two_out, three_out, inc_out;

ll ans[MAXN];

ll op_val[MAXOP];
int op_ind[MAXOP][3], op_offset[MAXOP][3], op_cnt[MAXOP];

ll get_val(int ind, int offset) {
	ll ans = 0ll;
	if (offset > 0) {
		REP(i, 0, offset) {
			ans += vals[ind][cur_cnt[ind] + i];
		}
	} else {
		REP(i, 0, -offset) {
			ans += vals[ind][cur_cnt[ind] - 1 - i];
		}
	}
	return ans;
}

void upd_val(int ind, int offset) {
	//printf("upd %d (%d): %d -> %d\n", ind, SZ(vals[ind]), cur_cnt[ind], cur_cnt[ind] + offset);
	
	if (cur_cnt[ind] == 2 || cur_cnt[ind] >= 4) {
		two_in.erase(mp(get_val(ind, -2), ind));
	}
	if (cur_cnt[ind] == 3) {
		three_in.erase(mp(get_val(ind, -3), ind));
	}
	if (cur_cnt[ind] >= 3) {
		inc_in.erase(mp(get_val(ind, -1), ind));
	}
	if (cur_cnt[ind] + 1 <= SZ(vals[ind]) && cur_cnt[ind] != 0) {
		inc_out.erase(mp(-get_val(ind, 1), ind));
	}
	if (cur_cnt[ind] + 2 <= SZ(vals[ind])) {
		two_out.erase(mp(-get_val(ind, 2), ind));	
	}
	if (cur_cnt[ind] + 3 <= SZ(vals[ind])) {
		three_out.erase(mp(-get_val(ind, 3), ind));
	}
	
	cur_cnt[ind] += offset;
	
	if (cur_cnt[ind] == 2 || cur_cnt[ind] >= 4) {
		two_in.insert(mp(get_val(ind, -2), ind));
	}
	if (cur_cnt[ind] == 3) {
		three_in.insert(mp(get_val(ind, -3), ind));
	}
	if (cur_cnt[ind] >= 3) {
		inc_in.insert(mp(get_val(ind, -1), ind));
	}
	if (cur_cnt[ind] + 1 <= SZ(vals[ind]) && cur_cnt[ind] != 0) {
		inc_out.insert(mp(-get_val(ind, 1), ind));
	}
	if (cur_cnt[ind] + 2 <= SZ(vals[ind])) {
		two_out.insert(mp(-get_val(ind, 2), ind));	
	}
	if (cur_cnt[ind] + 3 <= SZ(vals[ind])) {
		three_out.insert(mp(-get_val(ind, 3), ind));
	}
}

void set_op(int ind, vi vv) {
	op_cnt[ind] = SZ(vv);
	REP(i, 0, op_cnt[ind]) {
		op_offset[ind][i] = vv[i];
	}
}

vi tmp;

void solve(){
	int n, m;
	scanf("%d%d", &n, &m);
	REP(i, 0, n) {
		int c, v;
		scanf("%d%d", &c, &v);
		vals[c].pb(v);
	}
	int fl = 0;
	REPN(i, 1, m) {
		if (SZ(vals[i])) {
			SORT(vals[i]);
			reverse(BE(vals[i]));
			two_out.insert(mp(-get_val(i, 2), i));
			if (SZ(vals[i]) >= 3) {
				fl = 1;
				three_out.insert(mp(-get_val(i, 3), i));
			}
		}
	}
	REPN(i, 1, n) {
		ans[i] = -1;
	}
	if (!fl) {
		int cnt = 0;
		FA(it, two_out) {
			cnt += 2;
			ans[cnt] = ans[cnt - 2] + (-it->_1);
		}
		REPN(i, 1, n) {
			printf("%lld\n", ans[i]);
		}
		return;
	}
	
	set_op(0, {1});
	set_op(1, {2, -1});
	set_op(2, {3, -2});
	set_op(3, {2, 2, -3});
	
	//printf("%d %d %d %d %d %d\n", SZ(inc_out), SZ(two_out), SZ(three_out), SZ(inc_in), SZ(two_in), SZ(three_in));
	
	ans[2] = get_val(two_out.begin()->_2, 2);
	upd_val(two_out.begin()->_2, 2);
	
	REPN(i, 3, n) {
		
		/*REPN(j, 1, m) {
			printf("%d ", cur_cnt[j]);
		}
		putchar('\n');*/
		/*printf("*************** %d\n", i);
		REPN(j, 1, m) {
			if (cur_cnt[j]) {
				printf("%d ", cur_cnt[j]);
			}
		}
		putchar('\n');
		fflush(stdout);*/
		
		//printf("%d %d %d %d %d %d\n", SZ(inc_out), SZ(two_out), SZ(three_out), SZ(inc_in), SZ(two_in), SZ(three_in));
		
		/*if (i >= 4) {
			return;
		}*/
		
		REP(j, 0, MAXOP) {
			op_val[j] = -INF;
		}
		if (!inc_out.empty()) {
			op_val[0] = 0;
			op_ind[0][0] = inc_out.begin()->_2;
		}
		if (!two_out.empty() && !inc_in.empty()) {
			op_val[1] = 0;
			op_ind[1][0] = two_out.begin()->_2;
			op_ind[1][1] = inc_in.begin()->_2;
		}
		if (!three_out.empty() && !two_in.empty()) {
			op_val[2] = 0;
			op_ind[2][0] = three_out.begin()->_2;
			op_ind[2][1] = two_in.begin()->_2;
		}
		if (SZ(two_out) >= 2 && !three_in.empty()) {
			op_val[3] = 0;
			op_ind[3][0] = two_out.begin()->_2;
			op_ind[3][1] = (++(two_out.begin()))->_2;
			op_ind[3][2] = three_in.begin()->_2;
		}
		REP(j, 0, MAXOP) {
			if (op_val[j] == 0) {
				REP(k, 0, op_cnt[j]) {
					int sgn = (op_offset[j][k] > 0 ? 1 : -1);
					op_val[j] += sgn * get_val(op_ind[j][k], op_offset[j][k]);
				}
			}
		}
		int maxi = 0;
		REP(j, 0, MAXOP) {
			//printf("op %d - %lld\n", j, op_val[j]);
			if (op_val[maxi] < op_val[j]) {
				maxi = j;
			}
		}
		ans[i] = ans[i - 1] + op_val[maxi];
		REP(j, 0, op_cnt[maxi]) {
			upd_val(op_ind[maxi][j], op_offset[maxi][j]);
		}
	}
	REPN(i, 1, n) {
		printf("%lld\n", ans[i]);
	}
}   

int main(){

    //freopen(file".in", "r", stdin); freopen(file".out", "w", stdout);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();    
    }
}


Measured memory_bytes: 20736