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

typedef long long ll;

struct info {
	ll a;
	int w;
};

int main() {
	int n; ll c; scanf("%d%lld", &n, &c);
	vector <info> b(n);
	vector <ll> dp(n), m(500001, 0ll);

	ll M = 0;
	
	ll ans = 0ll;
	for(int i = 0, j = 0; i < n; ++i) {
		scanf("%lld%d", &b[i].a, &b[i].w);

		while(j < i && b[j].a < b[i].a) {
			m[b[j].w] = max(m[b[j].w], dp[j]);
			M = max(M, dp[j]);
			++j;
		}

		dp[i] = max(m[b[i].w] + b[i].a, M + b[i].a - c);
		ans = max(ans, dp[i]);
	}
	printf("%lld\n", ans);
	return 0;
}