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
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <bits/stdc++.h>
//#include <cassert>

const int inf = 2e9;
const long long ill = 4e18;
const long long mod = 998244353;
const long double eps = 1e-6;

#define pii pair<int, int>
#define tui tuple<int, int, ll>
typedef long long ll;
typedef long double ld;

using namespace std;

vector<pair<int, int>> a;

bool comp(tuple<int, int, ll, int> c, tuple<int, int, ll, int> d) {
	return a[get<0>(c)].first > a[get<0>(d)].first;
}

void solve() {
	for (int file = 1; file <=1; file++) {
		/*string fn = to_string(file);
		ifstream cin(fn+".in");*/
		int n, c;
		cin >> n>>c;
		a.resize(n);
		for (int i = 0; i < n; i++)
			cin >> a[i].first >> a[i].second;
		for (int i = 0; i < n; i++)
			a[i].second--;
		vector<vector<pair<ll, int>>> dp(n, vector<pair<ll, int>>(2, {-1, -1})); // dp[i][0] - don't take block into the set, dp[i][1] - take block into the set
		reverse(a.begin(), a.end());

		vector < vector<tuple<int, int, ll, int>>> blocks(500000); // starting cube, ending cube, sum of heights, colour
		int prev = -1, cur = -1;
		for (int i = 0; i < n; i++) {
			if (cur != a[i].first) {
				prev = cur;
				cur = a[i].first;
			}
			int color = a[i].second;
			if (!blocks[color].empty() && a[get<1>(blocks[color].back())].first == prev)
				blocks[color].back() = { get<0>(blocks[color].back()), i, a[i].first + get<2>(blocks[color].back()), color };
			else
				blocks[color].push_back({ i, i, a[i].first, color });

		}

		vector<tuple<int, int, ll, int>> fb;
		for (int i = 0; i < 500000; i++)
			for (auto &j : blocks[i])
				fb.push_back(j);
		sort(fb.begin(), fb.end(), comp);

		dp[0][1] = { get<2>(fb[0]), 0 }; // {value, no. block}
		dp[0][0] = { 0, -1 };
		for (int i = 1; i < fb.size(); i++) {
			if (dp[i][0].first < dp[i - 1][0].first)
				dp[i][0] = { dp[i - 1][0].first, dp[i - 1][0].second };
			if(dp[i][0].first < dp[i-1][1].first)
				dp[i][0] = { dp[i - 1][1].first, dp[i - 1][1].second };

			ll opt;
			ll interim;

			int ap, bp;

			if (dp[i - 1][0].second == -1)
				opt = dp[i - 1][0].first + get<2>(fb[i]);
			else {
				interim = ((get<3>(fb[i]) == get<3>(fb[dp[i - 1][0].second])) ? 0 : c);
				opt = dp[i - 1][0].first + get<2>(fb[i]) - interim;
			}
			if(dp[i-1][0].second!=-1)
				ap = a[get<1>(fb[dp[i - 1][0].second])].first;
			bp = a[get<0>(fb[i])].first;

			if (dp[i][1].first <= opt && (dp[i - 1][0].second == -1 || ap > bp))
				dp[i][1] = { opt, i };

			

			if (dp[i - 1][1].second == -1)
				opt = dp[i - 1][1].first + get<2>(fb[i]);
			else {
				interim = ((get<3>(fb[i]) == get<3>(fb[dp[i - 1][1].second])) ? 0 : c);
				opt = dp[i - 1][1].first + get<2>(fb[i]) - interim;
			}
			if (dp[i - 1][1].second != -1)
				ap = a[get<1>(fb[dp[i - 1][1].second])].first;
			bp = a[get<0>(fb[i])].first;

			if (dp[i][1].first <= opt && (dp[i - 1][1].second == -1 || ap > bp))
				dp[i][1] = { opt, i };


			opt = get<2>(fb[i]);
			if (dp[i][1].first < opt) {
				dp[i][1] = { opt, i };
			}
			
		}
		ll ans = max(dp[fb.size() - 1][0].first, dp[fb.size() - 1][1].first);
		/*ifstream ansin(fn + ".out");
		ll ans;
		ansin >> ans;*/
		cout << ans << '\n';
		/*if (ans != res)
			cout << "ERROR at test " << file << ". answer:" << ans << '\n';*/
		
	}
	
}

signed main() {
	ios_base::sync_with_stdio(0);
	int t = 1;
	//cin >> t;
	while (t--)
		solve();


}