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

#define st first
#define nd second

long long tree[3000000];
long long n, c, tree_size;
long long a[500005], w[500005]; 
long long result;
long long max_w;
vector<pair<long long, long long>> to_update;

void update(long long idx, long long val) {
    idx += tree_size - 1;
    tree[idx] = max(tree[idx], val);
    while (idx > 1) {
        idx /= 2;
        tree[idx] = max(tree[idx * 2], tree[idx * 2 + 1]);
    }
}

long long query(long long node, long long start, long long end, long long left, long long right) {
    if (left > end || right < start || left > right) return 0;
    if (left <= start && end <= right) return tree[node];
    long long mid = (start + end) / 2;
    return max(query(node * 2, start, mid, left, right), query(node * 2 + 1, mid + 1, end, left, right));
}

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

    cin >> n >> c;
    for (long long i = 1; i <= n; i++) {
        cin >> a[i] >> w[i];
        max_w = max(max_w, w[i]);
    }

    reverse(a + 1, a + n + 1);
    reverse(w + 1, w + n + 1);
    tree_size = 1 << (long long)ceil(log2(max_w));
    for (long long i = 1; i <= n; i++) {
        long long temp = max(
            query(1, 1, tree_size, w[i], w[i]), 
            max(
                query(1, 1, tree_size, 1, w[i] - 1), 
                query(1, 1, tree_size, w[i] + 1, tree_size)
            ) - c
        );
        to_update.push_back({w[i], temp + a[i]});
        if(i == n || a[i] != a[i + 1]) {
            for (auto [idx, val] : to_update) {
                update(idx, val);
            }
            to_update.clear();
        }
    }
    cout << tree[1] << endl;
}