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

std::map<int, std::multiset<int64_t>::iterator> W;
std::multiset<int64_t> S;
std::map<int, std::multiset<int64_t>::iterator> WE;
std::multiset<int64_t> SE;

int64_t getBestMatching(int w) {
    auto it = W.find(w);
    if (it == W.end()) return 0;
    return *(it->second);
}

int64_t getBestExcluding(int w) {
    auto it = W.find(w);
    int64_t excluded_score = -1;
    if (it != W.end()) {
        excluded_score = *(it->second);
        S.erase(it->second);
    }

    
    int64_t best_score = 0;
    if (S.rbegin() != S.rend()) best_score = *S.rbegin();

    if (it != W.end()) {
        it->second = S.insert(excluded_score);
    }

    return best_score;
}

void update(int w, int64_t s) {
    auto it = WE.find(w);
    if (it != WE.end() && s > *(it->second)) {
        SE.erase(it->second);
        it->second = SE.insert(s);
    } else {
        WE[w] = SE.insert(s);
    }
}

void transfer(int w, int64_t s) {
    auto it = W.find(w);
    if (it != W.end() && s > *(it->second)) {
        S.erase(it->second);
        it->second = S.insert(s);
    } else {
        W[w] = S.insert(s);
    }
}

void transfer() {
    while (!WE.empty()) {
        transfer(WE.begin()->first, *WE.begin()->second);
        SE.erase(WE.begin()->second);
        WE.erase(WE.begin());
    }
}

const int MAX = 500000+5;
int WW[MAX];
int64_t A[MAX];

int main() {
    std::ios_base::sync_with_stdio(0);

    int64_t c,a;
    int n, w;
    std::cin >> n >> c;

    auto it = S.insert(0);
    W[-1] = it;

    for (int i=0;i<n;++i)
        std::cin >> A[i] >> WW[i];
    for (int i=n-1;i>=0;--i) {
        w = WW[i];
        a = A[i];

        if (A[i] != A[i+1]) {
            transfer();
        }

        int64_t matching = getBestMatching(w);
        int64_t non_matching = getBestExcluding(w);
        // std::clog << a << " : " << w << " = " << matching << " or " << non_matching << std::endl;
        update(w, std::max(matching+a, non_matching-c+a));
    }
    transfer();

    std::cout << (S.rbegin() == S.rend() ? int64_t(0) : *S.rbegin()) << std::endl;

    return 0;
}