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
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll MINF = -1000000000000000000LL; // bardzo mała wartość

struct Block {
    int a, w;
};

struct Node {
    ll best, second;
    int best_pat;
};

struct SegTree {
    int size;
    vector<Node> tree;
    
    SegTree(int n) {
        size = 1;
        while(size < n) size *= 2;
        tree.assign(2 * size, {MINF, MINF, 0});
    }
    
    // Funkcja łącząca dwa węzły
    Node combine(const Node &L, const Node &R) {
        Node res;
        if(L.best > R.best) {
            res.best = L.best;
            res.best_pat = L.best_pat;
            res.second = max(L.second, R.best);
        } else if(L.best < R.best) {
            res.best = R.best;
            res.best_pat = R.best_pat;
            res.second = max(R.second, L.best);
        } else {
            res.best = L.best; // obie równe
            res.best_pat = L.best_pat; // dowolnie
            res.second = max(L.second, R.second);
        }
        return res;
    }
    
    // Aktualizacja pozycji idx (1-indexowane dla a)
    void update(int idx, ll val, int pat) {
        idx += size - 1;
        // Aktualizujemy, jeśli nowe dp jest większe
        if(val > tree[idx].best) {
            tree[idx].best = val;
            tree[idx].best_pat = pat;
        }
        // Przechodzimy do góry drzewa
        for(idx /= 2; idx >= 1; idx /= 2) {
            tree[idx] = combine(tree[2*idx], tree[2*idx+1]);
        }
    }
    
    // Zapytanie w przedziale [l, r] (1-indexowane)
    Node query(int l, int r) {
        Node resL = {MINF, MINF, 0}, resR = {MINF, MINF, 0};
        l += size - 1;
        r += size - 1;
        while(l <= r) {
            if(l % 2 == 1) {
                resL = combine(resL, tree[l]);
                l++;
            }
            if(r % 2 == 0) {
                resR = combine(tree[r], resR);
                r--;
            }
            l /= 2; r /= 2;
        }
        return combine(resL, resR);
    }
};

/// Struktura do zapytań per-wzór.
/// Dla każdego wzoru będziemy trzymać wektor par (a, prefix_max)
using Vec = vector<pair<int, ll>>;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, c;
    cin >> n >> c;
    vector<Block> blocks(n);
    for (int i = 0; i < n; i++){
        cin >> blocks[i].a >> blocks[i].w;
    }
    // Bloki są podane w kolejności niemalejącej – odwracamy, aby uzyskać malejący ciąg według a.
    reverse(blocks.begin(), blocks.end());
    
    // Maksymalna wartość a (zakres [1, MAXA])
    int MAXA = 500000;
    
    // Globalna struktura – segment tree – dla przedziałowych zapytań wg wartości a.
    SegTree seg(MAXA);
    
    // Struktury per-wzór: mapa wzoru -> wektor (a, prefix_max_dp)
    unordered_map<int, Vec> patMap;
    patMap.reserve(n*2);
    
    vector<ll> dp(n, 0);
    ll ans = 0;
    
    // Przetwarzamy bloki w kolejności: dla i od n-1 do 0.
    // Dzięki temu, dla danego bloku, już obliczone są dp dla bloków "wyżej" (mniejszych a).
    for (int i = n - 1; i >= 0; i--) {
        int a = blocks[i].a;
        int w = blocks[i].w;
        
        // Zapytanie w globalnym segtree dla przedziału [1, a-1]
        ll candidate_diff = MINF;
        if(a > 1) {
            Node node = seg.query(1, a - 1);
            // Jeśli najlepszy wynik globalny pochodzi z tego samego wzoru, używamy drugiego najlepszego.
            if(node.best_pat == w)
                candidate_diff = node.second - c;
            else
                candidate_diff = node.best - c;
        }
        
        // Zapytanie w strukturze dla wzoru w – binary search w wektorze (jeśli już istnieją klocki tego wzoru)
        ll candidate_same = MINF;
        if(patMap.find(w) != patMap.end()){
            Vec &vec = patMap[w];
            // Znajdź ostatni element z a < current a.
            auto it = std::lower_bound(vec.begin(), vec.end(), make_pair(a, (ll) -1),
                                       [](const pair<int,ll> &p, const pair<int,ll> &q) {
                                           return p.first < q.first;
                                       });
            if(it != vec.begin()){
                it--;
                candidate_same = it->second;
            }
        }
        
        ll candidate = max(candidate_same, candidate_diff);
        if(candidate < 0) candidate = 0;
        dp[i] = a + candidate;
        ans = max(ans, dp[i]);
        
        // Aktualizacja globalnego segment tree: w pozycji a przechowujemy maksymalne dp dla danego a.
        seg.update(a, dp[i], w);
        
        // Aktualizacja struktury per-wzór: dodajemy parę (a, nowy prefix_max)
        {
            Vec &vec = patMap[w]; // operator [] utworzy wektor, jeśli nie istniał
            ll newVal = dp[i];
            if(!vec.empty())
                newVal = max(newVal, vec.back().second);
            vec.push_back({a, newVal});
        }
    }
    
    cout << ans << "\n";
    return 0;
}