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
#include <bits/stdc++.h>
using namespace std;

template<typename T> void uniq(vector<T>& a){
	a.resize(unique(a.begin(), a.end()) - a.begin());
}

using ll = int64_t;
int main(){
	ios_base::sync_with_stdio(false), cin.tie(nullptr);
	int N, C;
	cin >> N >> C;
	int D = 5.01e5;
	vector<vector<int> > pattern(D);
	for(int i = 0; i < N; i++){
		int a, w;
		cin >> a >> w;
		pattern[a].push_back(w);
	}
	ll gbest = 0;
	map<int, ll> dp;

	for(int d = 0; d < D; d++){
		if(pattern[d].empty()) continue;
		sort(pattern[d].begin(), pattern[d].end());
		uniq(pattern[d]);
		ll score = d - C;
		for(int a : pattern[d]){
			dp[a] = max(dp[a], max(gbest, dp[a] + C) + score);
		}
		for(int a : pattern[d]){
			gbest = max(gbest, dp[a]);
		}

	}
	ll ans = max(ll(0), gbest);
	cout << ans << '\n';
}