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

using namespace std;

void mergePrizes(unordered_map<long long, long long> &prizes, unordered_map<long long, long long> &tmpPrizes, pair<long long, long long> top2[2]) {
    for (auto [a, b] : tmpPrizes) {
        prizes[a] = b;
        if (b > top2[0].second) {
            top2[1] = top2[0];
            top2[0] = {a, b};
        } else if (b > top2[1].second) {
            top2[1] = {a, b};
        }
    }
    tmpPrizes.clear();
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n, c;
    cin >> n >> c;
    vector<pair<long long, long long>> bricks;
    bricks.resize(n);
    for (long long i = 0; i < n; ++i) {
        cin >> bricks[i].second >> bricks[i].first;
    }
    pair<long long, long long> top2[2]{};
    unordered_map<long long, long long> prizes;

    auto brick = bricks.rbegin();
    long long lastBrickSize = 1'000'000;
    unordered_map<long long, long long> tmpPrizes;
    while (brick != rend(bricks)) {
        if (brick->second < lastBrickSize) {
            mergePrizes(prizes, tmpPrizes, top2);
            lastBrickSize = brick->second;
        }
        long long colorCandidate = prizes[brick->first] + brick->second;
        int nonColorTop = top2[0].first != brick->first ? 0 : 1;
        long long nonColorCandidate = max(0ll, top2[nonColorTop].second - c) + brick->second;
        tmpPrizes[brick->first] = max(max(prizes[brick->first], colorCandidate), nonColorCandidate);
        ++brick;
    }
    mergePrizes(prizes, tmpPrizes, top2);
    cout << top2[0].second;
}