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
// PA2025 runda 3B - https://sio2.mimuw.edu.pl/c/pa-2025-1/p/mno/
//-std=c++20
#include<iostream>
#include<vector>
#include<list>
#include<algorithm>

using namespace std;
struct color_t {
    int64_t w;
    int64_t previous;
    int64_t current;
};
struct frame_t {
    int64_t no;
    list<color_t> colors;
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int64_t n, c;
    cin >> n >> c;
    vector<int64_t> cummulative;
    cummulative.resize(50000);
    list<frame_t> frames;
    for (int i = 0; i < n; i++) {
        int64_t ai, wi;
        cin >> ai >> wi;
        wi--;
        color_t col{wi, cummulative[wi], cummulative[wi] + ai};
        cummulative[wi] += ai;
        if (frames.empty() || frames.back().no < ai) {
            frame_t f = {ai};
            frames.push_back(f);
            frames.back().colors.push_back(col);
        } else {
            frames.back().colors.push_back(col);
        }
    }
    auto it = frames.end();
    int64_t best_score = 0;
    int64_t best_color;
    int64_t potential_loss;
    it--;
    for (auto &col: it->colors) {
        if (col.current > best_score) {
            best_score = col.current;
            best_color = col.w;
            potential_loss = col.previous;
        }
    }
    while (it != frames.begin()) {
        it--;
        int64_t new_score = 0;
        int64_t new_potential_loss = potential_loss;
        int64_t new_best_color = best_color;
        for (auto &col: it->colors) {
            if (col.w == best_color) {
                new_potential_loss = col.current;
            }
        }
        for (auto &col: it->colors) {
            if (col.w == best_color) {
                continue;
            }
            if (best_score+col.current - potential_loss - c > new_score) {
                new_score = best_score+col.current - potential_loss - c;
                new_potential_loss = col.previous;
                new_best_color = col.previous;
            }
        }
        if (new_score > best_score) {
            best_score = new_score;
            potential_loss = new_potential_loss;
            best_color = new_best_color;
        }
    }

    cout << best_score;

}