1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
using namespace std;

int a[5000003], w[5000003], sumy[500003];
bool takisam(int i){
	int j = i + 1;
	if (a[j] > 0 && w[j] == w[i])  return true;
	while(a[j] == 0) {
		if (w[j] == w[i]) return true;
		j++;
	}
	return false;
}
int main(){
	ios_base::sync_with_stdio(0);
	long long wyn = 0;
	int n, c, i, a1, w1, j = 2, m, maks = 0, imaks = 0;
	cin >> n >> c;
	cin >> a[1] >> w[1];
	sumy[w[1]] = a[1];
	for(i = 2; i <= n; i++){
		cin >> a1 >> w1;
		sumy[w1] += a1;
		if (w1 == w[j-1]) {
			a[j-1] = a[j-1] + a1;
		}
		else {
			a[j] = a1;
			w[j] = w1;
			j++;
		}		
	} 
	m = j-1; a[m + 1] = 1;
	for(i = 1; i <= m; i++){
		if (a[i] > maks) {
			maks = a[i];
		}
	}
	if (c > maks) {
		for(i = 1; i <= 500000; i++) maks = max(maks, sumy[i]);
		cout << maks;
		return 0;
	}
	w[m+1] = w[m];
	for(i = m; i > 0; i--){
		if(takisam(i)) wyn = wyn + a[i];
		else {
			if (a[i] - c < 0) {
			w[i] = w[i+1];
			a[i] = 0;
		}
			else if ( a[i] - c == 0){
			a[i] = 0;
		}
			else wyn = wyn + a[i] - c;
		}
		//cout << wyn << endl;
	}
	
	cout << wyn << endl;
	
return 0;
}