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>
#define ll long long
using namespace std;

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

	ll n, c; cin>>n>>c;
	vector<pair<ll, ll>> datei(n); for(auto &e: datei) cin>>e.first>>e.second;
	sort(datei.begin(), datei.end());

	vector<ll> ans(500'001, 0);

	ll last = -1, maxi = 0;
	queue<pair<ll, ll>> upd;

	for(auto e: datei){
		if(e.first != last){
			while(!upd.empty()){
				ans[upd.front().first] = max(ans[upd.front().first], upd.front().second);
				maxi = max(maxi, ans[upd.front().first]);
				upd.pop();
			}
			last = e.first;
		}

		upd.push({e.second, max(ans[e.second]+e.first, maxi+e.first-c)});
	}

	while(!upd.empty()){
		maxi = max(maxi, upd.front().second);
		upd.pop();
	}

	cout<<maxi;
	return 0;
}