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

using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define pb push_back
#define st first
#define nd second
const int MAXN = 1 << 19;
ll seg[2 * MAXN];
ll maks[MAXN];
pair<ll, int> T[MAXN];

void upd(int l, int r, ll x) {
    l += MAXN;
    r += MAXN;
    while (l < r) {
        if (l % 2 == 1) {
            seg[l] = max(seg[l], x);
            l++;
        }
        if (r % 2 == 0) {
            seg[r] = max(seg[r], x);
            r--;
        }
        l /= 2;
        r /= 2;
    }
    if (l == r) {
        seg[l] = max(seg[l], x);
    }
}

ll ans(int v) {
    v += MAXN;
    ll ile = 0;
    while (v > 0) {
        ile = max(ile, seg[v]);
        v /= 2;
    }
    return ile;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    ll c;
    cin >> n >> c;
    rep(i, n) {
        cin >> T[i].st >> T[i].nd;
    }
    int i = 0;
    while (i < n) {
        int j = i;
        vector<ll> odp;
        while (j < n && T[j].st == T[i].st) {
            // cout << "j = " << j << " maks = " << maks[j] << " ans = " << ans(j) - c << '\n';
            odp.pb(max(maks[T[j].nd], ans(T[j].nd) - c));
            j++;
        }
        j--;
        int sz = odp.size();
        rep(it, sz) {
            int wzor = T[i + it].nd;
            maks[wzor] = max(maks[wzor], odp[it] + T[i + it].st);
            upd(0, wzor - 1, maks[wzor]);
            upd(wzor + 1, MAXN - 1, maks[wzor]);
        }
        i = j + 1;
    }
    ll wyn = 0;
    for (int i = 1; i < MAXN; i++) {
        wyn = max(wyn, maks[i]);
    }
    cout << wyn << '\n';
    return 0;
}