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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL INF = LONG_LONG_MAX/2;
const int NAX = 5e5 + 10;

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

	int N, C;
	cin >> N >> C;
	vector<int> A(N), W(N);
	for (int i = 0; i < N; i++)
		cin >> A[i] >> W[i];
	vector<LL> DP(N), BEST(NAX, -INF);
	LL BEST_ALL = -INF;
	for (int i = N-1; i >= 0; i--)
	{
		if (i == N-1 || A[i] != A[i+1])
		{
			for (int j = i; j >= 0 && A[i] == A[j]; j--)
				DP[j] = A[j] + max(0ll, max(BEST[W[j]], BEST_ALL - C));
			for (int j = i; j >= 0 && A[i] == A[j]; j--)
			{
				BEST_ALL = max(BEST_ALL, DP[j]);
				BEST[W[j]] = max(BEST[W[j]], DP[j]);
			}
		}
	}
	cout << *max_element(DP.begin(), DP.end()) << "\n";
}