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>
#define ll long long
using namespace std;

const int N = 5e5;

int n, c, a[N+2], w[N+2], base = 1, max_w;
ll tree[4*N+2], res[N+2], final_res;

void update(int x, ll val) {
    x += base - 1;
    if (val < tree[x]) return;
    tree[x] = val;
    while(x > 1) {
        x /= 2;
        tree[x] = max(tree[2*x], tree[2*x+1]);
    }
}

ll max_val(int v, int l, int r, int a, int b) {
    if(b < l || a > r || l > r) return 0;
    if(a >= l && b <= r) return tree[v];
    int mid = (a + b) / 2;
    return max(max_val(v*2, l, r, a, mid), max_val(v*2+1, l, r, mid+1, b));
}

int main() {
    cin>>n>>c;

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

    while (base < max_w) base *= 2;

    for(int i = 1 ; i<=n ; i++) {
        int temp = i;
        for(int j = i ; j<=n && a[j] == a[i] ; j++) {
            ll val1 = max_val(1, 1, w[j] - 1, 1, base);
            ll val2 = max_val(1, w[j] + 1, base, 1, base);

            ll val3 = max_val(1, w[j], w[j], 1, base);

            res[j] = max(max(val1, val2) - c, val3) + a[j];
        }

        for(int j = i ; j<=n && a[j] == a[i] ; j++) {
            update(w[j], res[j]);
            temp = j;
        }
        i = temp;
    }

    cout<<tree[1]<<"\n";
}