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
84
#include <bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pb push_back
#define pf push_front
#define in insert
#define f first
#define s second
#define pii pair<int, int>
#define pib pair<int, bool>
#define cint const int
#define nw '\n'
#define sp " "
#define mn 500009
#define inf 1000000000000000009
#define ms 25000009
#define mn2 524288
using namespace std;
int n, c, dp[mn], wyn;
ll tree[2*mn2];
pii tab[mn];
set<pii> el;
void update(int pos, ll val){
    pos+=mn2;
    tree[pos]=val;
    for(pos>>=1; pos>=1; pos>>=1){
        tree[pos]=max(tree[pos*2], tree[(pos*2)+1]);
    }
}
ll query(int l, int r){
    l+=mn2;
    r+=mn2;
    ll mik=-inf;
    while(l<=r){
        if(l%2==1) mik=max(mik, tree[l++]);
        if(r%2==0) mik=max(mik, tree[r--]);
        l>>=1;
        r>>=1;
    }
    return mik;
}
int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>c;
    for(int i=0; i<n; ++i) cin>>tab[i].f>>tab[i].s;
    for(int i=0; i<2*mn2; ++i) tree[i]=-inf;
    vector<int> v;
    unordered_map<int, vector<pair<int, ll>>> mxdp;
    ll mxwyn=0;
    for(int i=0; i<n; ++i){
        int ai=tab[i].f, wi=tab[i].s;
        int l=upper_bound(v.begin(), v.end(), ai-1)-v.begin();
        ll mxa=-inf;
        if(l>0) mxa=query(0, l-1);
        ll mxw=0;
        auto& list=mxdp[wi];
        if(!list.empty()){
            int left=0, right=(int)list.size()-1;
            int bes=-1;
            while(left<=right){
                int mid=(left+right)/2;
                if(list[mid].f<ai){ bes=mid; left=mid+1; }
                else right=mid-1;
            }
            if(bes!=-1) mxw=list[bes].s;
        }
        ll smxw=(mxa!=-inf) ? (mxa-c) : -inf;
        ll roz=max(smxw, mxw);
        ll dpi=ai+max(roz, 0LL);
        update(i, dpi);
        if(list.empty()) list.emplace_back(ai, dpi);
        else{
            if(ai>=list.back().f){
                ll nmx=max(list.back().s, dpi);
                list.emplace_back(ai, nmx);
            }
            else assert(false);
            // błąd, do tego nie ma nigdy dojść
        }
        v.pb(ai);
        mxwyn=max(mxwyn, dpi);
    }
    cout<<mxwyn;
}