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
#include <iostream>
#include <vector>
#include <map>

using namespace std;

long long int n, a, w;
long long int c;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> c;
	vector < pair<long long int, vector<long long int>>> cube;
	for (int i = 0; i < n; ++i) {
		cin >> a >> w;
		if(cube.size()==0){
			vector<long long int> tmp;
			tmp.push_back(w);
			cube.push_back(make_pair(a, tmp));
			continue;
		}
		if (cube[cube.size() - 1].first == a)
			cube[cube.size() - 1].second.push_back(w);
		else {
			vector<long long int> tmp;
			tmp.push_back(w);
			cube.push_back(make_pair(a, tmp));
		}
	}

	map<int, long long int> prev_row;
	vector <map<int, long long int>> rows;
	map<int, int> last_known_row;

	long long int prev_max = 0, curr_max=0;
	long long int v;

	for (int i = 0; i < cube.size(); ++i) {
		map<int, long long int> curr_row;
		for (int j = 0; j < cube[i].second.size(); ++j) {
			long long int value = cube[i].first;
			int color = cube[i].second[j];

			if (last_known_row.find(color) != last_known_row.end()) {
				v = value + max(rows[last_known_row[color]][color], max((long long int)0, (prev_max - c)));
			}
			else {
				v = value + max((long long int)0, (prev_max - c));
			}
			curr_row[color] = v;
			curr_max = max(curr_max, v);
			last_known_row[color] = rows.size();
		}
		rows.push_back(curr_row);
		prev_row = rows[rows.size() - 1];
		prev_max = curr_max;
		curr_max = 0;		
	}
	long long int result = 0;
	for (auto r : prev_row)
		result = max(result, r.second);

	cout << result <<endl;
	return 0;
}