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

using ll = long long;

struct Segment_Tree {
    int p, M;
    vector <long long> tree;

    Segment_Tree(int n) {
        p = 1;
        while (!((1 << p) - (1 << (p - 1)) >= n)) p++;
        M = (1 << (p - 1));
        tree.resize(1 << p, 0);
    }

    Segment_Tree(vector <int> &v) {
        int n = (int)v.size();
        p = 1;
        while (!((1 << p) - (1 << (p - 1)) >= n)) p++;
        M = (1 << (p - 1));
        tree.resize(1 << p, 0);
        for (int i = 0; i < n; i++)
            tree[i + M] = v[i];
        
        for (int i = M - 1; i >= 1; i--)
            tree[i] = max(tree[2 * i], tree[2 * i + 1]);
    }

    long long query(int a, int b) {
        a += M;
        b += M;
        long long ans = tree[a];
        if (a != b) ans = max(ans, tree[b]);
        while (a / 2 != b / 2) {
            if (a % 2 == 0) ans = max(ans, tree[a + 1]);
            if (b % 2 == 1) ans = max(ans, tree[b - 1]);
            a /= 2;
            b /= 2;
        }
        return ans;
    }

    void update(int a, long long v) {
        a += M;
        tree[a] = v;
        a /= 2;
        while (a) {
            tree[a] = max(tree[2 * a], tree[2 * a + 1]);
            a /= 2;
        }
    }
};

const int MAXW = 5e5;

int main() {
    int n;
    ll c;
    cin >> n >> c;
    Segment_Tree dp(MAXW + 2);
    vector <vector <pair <ll, ll>>> v;
    for (int i = 0; i < n; i++) {
        ll a, w;
        cin >> a >> w;
        if (!v.empty() && v.back().back().first == a) v.back().push_back({a, w});
        else v.push_back({{a, w}});
    }

    for (auto &vec : v) {
        vector <pair <int, ll>> change;
        for (auto &[a, b] : vec) {
            ll cur0 = max(dp.query(0, b - 1), dp.query(b + 1, MAXW + 1)) + a - c;
            ll cur1 = dp.query(b, b) + a;
            change.push_back({b, max(cur0, cur1)});
        }

        for (auto &[a, b] : change) {
            if (dp.query(a, a) < b) dp.update(a, b);
        }
    }
    cout << dp.query(1, MAXW) << '\n';
}