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
#include <bits/stdc++.h>

typedef long long ll;

#define f first
#define s second

using namespace std;

constexpr int N = 5e5 + 10;

long long score[N];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, c, a, w;
    vector<pair<int, int>> blocks;
    vector<pair<int, long long>> tmp;
    cin >> n >> c;
    for (int i = 0; i < n; i++) {
        cin >> a >> w;
        blocks.push_back({a, w});
    }
    long long best_score = 0;
    int pattern = -1;
    tmp.push_back({blocks.back().s, blocks.back().f});
    for (int i = (int)blocks.size() - 2; i >= 0; i--) {
        if (blocks[i].f != blocks[i + 1].f) {
            for (auto p : tmp) {
                score[p.f] = p.s;
                if (score[p.f] > best_score) {
                    best_score = p.s;
                    pattern = p.f;
                }
            }
            tmp.clear();
        }
        if (pattern != blocks[i].s && score[blocks[i].s] < best_score - c)
            tmp.push_back({blocks[i].s, best_score + blocks[i].f - c});
        else
            tmp.push_back({blocks[i].s, score[blocks[i].s] + blocks[i].f});
    }
    for (auto p : tmp) {
        score[p.f] = p.s;
        if (score[p.f] > best_score) {
            best_score = p.s;
            pattern = p.f;
        }
    }
    cout << best_score << "\n";
    return 0;
}