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

#define all(a) begin(a), end(a)
using ll = long long;

constexpr ll inf = 1e18;
void solve() {
    ll n, c;
    cin >> n >> c;

    vector<pair<ll, ll>> a(n);
    for (auto &[a, w] : a)
        cin >> a >> w;

    map<int, map<ll, ll>> pref;
    auto get_smaller = [](map<ll, ll> const &m, ll x) {
        auto it = m.lower_bound(x);
        if (it == m.begin())
            return -inf;
        return prev(it)->second;
    };

    auto insert = [](map<ll, ll> &m, ll k, ll v) {
        v = max(v, 0ll);

        auto it = m.lower_bound(k);
        if (it != m.begin())
            v = max(v, prev(it)->second);

        ll &t = m[k];
        t = max(t, v);
    };

    for (auto [a, w] : a) {
        ll cur = a;
        cur = max(cur, get_smaller(pref[-1], a) + a - c);
        cur = max(cur, get_smaller(pref[w], a) + a);

        insert(pref[w], a, cur);
        insert(pref[-1], a, cur);
    }

    cout << pref[-1].rbegin()->second << "\n";
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int tests = 1;
    // cin >> tests;

    while (tests--)
        solve();
}