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
#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>

using namespace std;

typedef pair<int,int> pii;

const int BASE = 1<<19;

vector<pii> blocks;
int height[2*BASE] {};

void set(int p, int val){
    p += BASE;
    height[p] = val;
    while(p > 0){
        p >>= 1;
        height[p] = max(height[2*p], height[2*p+1]);
    }
}

int query(int p, int q){
    int ret = 0;
    p += BASE -1;
    q += BASE +1;
    while(p>>1 != q>>1){
        if(!(p&1)){
            ret = max(ret, height[p+1]);
        }
        if(q&1){
            ret = max(ret, height[q-1]);
        }
        p >>= 1;
        q >>= 1;
    }
    return ret;
}



bool cmp(pii l, pii r){
    return l.first > r.first;
}

int main(){
    int n, c;
    cin >> n >> c;
    for(int i = 0; i < n; i++){
        int a, w;
        cin >> a >> w;
        blocks.push_back({a,w});
    }

    sort(blocks.begin(),blocks.end(),cmp);

    for(int i = 0; i < blocks.size(); i++){
        int a, w;
        tie(a, w) = blocks[i];
        int same = query(w,w);
        int diff = max(query(0,w-1),query(w+1,BASE));

        set(w, max(same + a, diff + a - c));

        // cout << a << " " << w << ": " << endl;
        // cout << same << " " << diff << endl;
        // cout << same + a << " " <<  diff + a - c << "; max " <<  max(same + a, diff + a - c) << endl;
        // cout << query(0,BASE) << endl << endl;
    }
    
    cout << query(0,BASE);

    return 0;
}