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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
// MagicDark
#include <bits/stdc++.h>
#define debug cerr << "\33[32m[" << __LINE__ << "]\33[m "
#define SZ(x) ((int) x.size() - 1)
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> T& chkmax(T& x, T y) {return x = max(x, y);}
template <typename T> T& chkmin(T& x, T y) {return x = min(x, y);}
template <typename T> T& read(T &x) {
	x = 0; int f = 1; char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
	return x *= f;
}
const int N = 5e5 + 10;
int n, c, a[N], w[N];
ll f[N];
// struct Info {
// 	ll mx1;
// 	int id;
// 	ll mx2;
// 	friend Info operator + (Info x, Info y) {
// 		if (x.mx1 > y.mx1) {
// 			return (Info) {x.mx1, x.id, max(x.mx2, y.id == x.id ? y.mx2 : y.mx1)};
// 		}
// 		return (Info) {y.mx1, y.id, max(y.mx2, x.id == y.id ? x.mx2 : x.mx1)};
// 	}
// } O;
struct BIT {
	ll t[N];
	void modify(int x, ll y) {
		for (; x; x ^= x & -x) chkmax(t[x], y);
	}
	ll query(int x) {
		ll s = 0;
		for (; x < N; x += x & -x) chkmax(s, t[x]);
		return s;
	}
} ds;
ll mx;
int lst[N];
signed main() {
	read(n), read(c);
	F(i, 1, n) {
		read(a[i]), read(w[i]);
	}
	reverse(a + 1, a + n + 1);
	reverse(w + 1, w + n + 1);
	F(i, 1, n) {
		if (a[lst[w[i]]] == a[i]) continue;
		f[i] = a[i];
		chkmax(f[i], ds.query(a[i] + 1) - c + a[i]);
		if (lst[w[i]]) chkmax(f[i], f[lst[w[i]]] + a[i]);
		// if (x.id == w[i]) {
		// 	f[i] = max(x.mx1 - c, x.mx2) + a[i];
		// } else {
		// 	f[i] = x.mx1 + a[i];
		// }
		chkmax(mx, f[i]);
		// Info t;
		// t.mx1 = f[i], t.id = w[i], t.mx2 = 0;
		ds.modify(a[i], f[i]);
		lst[w[i]] = i;
	}
	cout << mx;
	return 0;
}
/* why?
*/