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
#include <bits/stdc++.h>
#define nl '\n'

using namespace std;
using ll = long long;
const int MAXN = 5e5+1;

unordered_map<ll, priority_queue<ll>> dp_color;

priority_queue<ll> dp;

vector<vector<ll>> by_height(MAXN);

int main()
{
	cin.tie(0)->sync_with_stdio(0);
	int n, c;
	cin>>n>>c;
	for(int i=0; i<n; i++){
		ll a, w;
		cin>>a>>w;
		by_height[a].push_back(w);
		if(!dp_color[w].size()){ dp_color[w].push(0); }
	}
	dp.push(0);
	for(int i=MAXN-1; i>0; i--){
		vector<pair<ll, ll>> dp_add;
		for(auto w: by_height[i]){
			//cerr<<dp.top()-c<<' '<<dp_color[w].top()<<nl;
			dp_add.push_back({w, i+max(dp.top()-c, dp_color[w].top())});
		}
		for(auto [w, res]: dp_add){
			dp_color[w].push(res);
			dp.push(res);
		}
	}
	cout<<dp.top()<<nl;
	return 0;
}