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;
typedef vector<int> VI;
typedef pair <int,int> ii;
typedef long long LL;
#define pb push_back
const int INF = 2147483647;
const int N = 500005;

int last[N], i, n, c, a[N], w[N], j, k;
LL tab[N], bat[N], preMax;

int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> c;
for (i=1;i<=500000;i++) last[i] = -1;
for (i=1;i<=n;i++) cin >> a[i] >> w[i];
i = 1;
preMax = 0;
while (i <= n) {
	j = i;
	while (j + 1 <= n && a[j + 1] == a[i]) j++;
	for (k=i;k<=j;k++) {
		if (last[w[k]] == -1) bat[k] = preMax + a[k] - c; else bat[k] = max(preMax + a[k] - c, bat[last[w[k]]] + a[k]);
		bat[k] = max(bat[k], a[k] * 1LL);
		tab[k] = max(bat[k], preMax);
	}
	for (k=i;k<=j;k++) {
		last[w[k]] = k;
		preMax = max(preMax, tab[k]);
	}
	i = j + 1;
}
cout << preMax << endl;
return 0;
}