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
#include <cstdio>
#include <cstdint>
#include <vector>
#include <set>

using namespace std;

int main () {
	int n, c, a, w, i;
	int64_t best_total, score_same, score_different;
	best_total = -1;
	vector<int64_t> best(500008, -1);
	vector<set<int> > levels(500008, set<int>());
	vector<pair<int, int64_t> > update;
	scanf("%d %d", &n, &c);
	for (i = 0; i < n; ++i) {
		scanf("%d %d", &a, &w);
		levels[a].insert(w);
	}
	for (a = 500004; a > 0; --a) {
		update.clear();
		update.reserve(levels[a].size() + 8);
		for (set<int>::iterator it = levels[a].begin(); it != levels[a].end(); it++) {
			score_same = best[*it] == -1 ? a : best[*it] + a;
			score_different = best_total == -1 ? a : best_total + a - c;
			if (score_same > score_different) {
				update.push_back(make_pair(*it, score_same));
			}
			else if (score_different > best[*it]) {
				update.push_back(make_pair(*it, score_different));
			}
		}
		for (vector<pair<int, int64_t> >::iterator it = update.begin(); it != update.end(); it++) {
			best[it->first] = it->second;
			if (it->second > best_total) {
				best_total = it->second;
			}
		}
	}
	printf("%lld\n", best_total);
	return 0;
}