// Never let them see you bleed...

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, int> pli;

const int maxn = 2e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10;

vector<ll> v[maxn];
vector<pli> a;
int cnt[maxn];
int pt[maxn];
ll bst[maxn], indiv[maxn];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();

    int n, k;
    cin >> n >> k;
    for(int i = 0; i < n; i++){
	int a, b;
	cin >> a >> b;
	v[--a].PB(2*b);
    }
    for(int i = 0; i < k; i++){
	sort(v[i].begin(), v[i].end(), greater<ll>());
	assert(sz(v[i]) >= 2);
	ll avg = (v[i][0] + v[i][1]) / 2;
	v[i][0] = v[i][1] = avg;
	for(ll x : v[i])
	    a.PB({x, i});
    }
    sort(a.begin(), a.end(), greater<pli>());
    for(int i = 0; i < k; i++){
	v[i].clear();
    }
    bst[n] = -1;
    for(int i = n-1; i >= 0; i--){
	int c = a[i].S;
	ll num = -1;
	v[c].PB(a[i].F);
	if(sz(v[c]) >= 3)
	    num = v[c][sz(v[c])-1] + v[c][sz(v[c])-2] + v[c][sz(v[c])-3];
	bst[i] = max(bst[i+1], num);
    }
    for(int i = 0; i < k; i++){
	reverse(v[i].begin(), v[i].end());
    }
    
    multiset<ll> st;
    for(int i = 0; i < n; i++){
	int c = a[i].S;
	if(st.empty())
	    indiv[i] = -1;
	else
	    indiv[i] = *st.rbegin();
	if(++pt[c] >= 2){
	    if(pt[c] != 2)
		st.erase(st.find(v[c][pt[c]-1]));
	    if(pt[c] != sz(v[c]))
		st.insert(v[c][pt[c]]);
	}
    }
    
    ll sum = 0, lst = -1;
    for(int i = 0; i < n; i++){
	cnt[a[i].S]++;
	sum+= a[i].F;
	ll ans = -2;
	if(cnt[a[i].S] > 2){
	    lst = a[i].F;
	}
	if(cnt[a[i].S] == 1){
	    if(lst != -1)
		ans = max(ans, sum + a[i].F - lst);
	    if(i > 1 && cnt[ a[i-1].S ] == 2 && a[i-1].S == a[i-2].S && bst[i-2] != -1)
		ans = max(ans, sum - a[i].F - a[i-1].F - a[i-2].F + bst[i-2]);
	    if(indiv[i] != -1)
		ans = max(ans, sum - a[i].F + indiv[i]);
	}
	else{
	    ans = sum;
	}
	cout << ans/2 << "\n";
    }
    return 0;    
}

### Prompt

Create a solution in CPP for 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
// Never let them see you bleed...

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, int> pli;

const int maxn = 2e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10;

vector<ll> v[maxn];
vector<pli> a;
int cnt[maxn];
int pt[maxn];
ll bst[maxn], indiv[maxn];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();

    int n, k;
    cin >> n >> k;
    for(int i = 0; i < n; i++){
	int a, b;
	cin >> a >> b;
	v[--a].PB(2*b);
    }
    for(int i = 0; i < k; i++){
	sort(v[i].begin(), v[i].end(), greater<ll>());
	assert(sz(v[i]) >= 2);
	ll avg = (v[i][0] + v[i][1]) / 2;
	v[i][0] = v[i][1] = avg;
	for(ll x : v[i])
	    a.PB({x, i});
    }
    sort(a.begin(), a.end(), greater<pli>());
    for(int i = 0; i < k; i++){
	v[i].clear();
    }
    bst[n] = -1;
    for(int i = n-1; i >= 0; i--){
	int c = a[i].S;
	ll num = -1;
	v[c].PB(a[i].F);
	if(sz(v[c]) >= 3)
	    num = v[c][sz(v[c])-1] + v[c][sz(v[c])-2] + v[c][sz(v[c])-3];
	bst[i] = max(bst[i+1], num);
    }
    for(int i = 0; i < k; i++){
	reverse(v[i].begin(), v[i].end());
    }
    
    multiset<ll> st;
    for(int i = 0; i < n; i++){
	int c = a[i].S;
	if(st.empty())
	    indiv[i] = -1;
	else
	    indiv[i] = *st.rbegin();
	if(++pt[c] >= 2){
	    if(pt[c] != 2)
		st.erase(st.find(v[c][pt[c]-1]));
	    if(pt[c] != sz(v[c]))
		st.insert(v[c][pt[c]]);
	}
    }
    
    ll sum = 0, lst = -1;
    for(int i = 0; i < n; i++){
	cnt[a[i].S]++;
	sum+= a[i].F;
	ll ans = -2;
	if(cnt[a[i].S] > 2){
	    lst = a[i].F;
	}
	if(cnt[a[i].S] == 1){
	    if(lst != -1)
		ans = max(ans, sum + a[i].F - lst);
	    if(i > 1 && cnt[ a[i-1].S ] == 2 && a[i-1].S == a[i-2].S && bst[i-2] != -1)
		ans = max(ans, sum - a[i].F - a[i-1].F - a[i-2].F + bst[i-2]);
	    if(indiv[i] != -1)
		ans = max(ans, sum - a[i].F + indiv[i]);
	}
	else{
	    ans = sum;
	}
	cout << ans/2 << "\n";
    }
    return 0;    
}

```