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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <bits/stdc++.h>
using namespace std;

// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2")

#define LL long long
#define int long long

struct Tree_Get_Max {
    using T = int ;
    T f(T a , T b) { return max (a , b); }
    const T zero = 0;
    vector <T > tree ;
    int sz = 1;
    Tree_Get_Max ( int n) {
        while ( sz < n)
            sz *= 2;
        tree.resize ( sz * 2, zero );
    }
    void update ( int pos , T val ) {
    tree [ pos += sz ] = val ;
        while ( pos /= 2)
        tree [ pos ] = f( tree [ pos * 2] , tree [ pos * 2 +1]);
    }
    T get ( int l , int r) {
        l += sz , r += sz ;
        if (l == r)
        return tree [l ];
        T ret_l = tree [l], ret_r = tree [r ];
        while (l + 1 < r) {
            if (l % 2 == 0)
            ret_l = f( ret_l , tree [l + 1]) ;
            if (r % 2 == 1)
            ret_r = f( tree [r - 1] , ret_r );
            l /= 2, r /= 2;
        }
        return f( ret_l , ret_r );
    }
};

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

    int N = 500002;
    Tree_Get_Max tree(N);

    int prev = -1;
    queue<int> klocki;
    for(int t=0;t<n;t++){
        int a,b;
        cin>>a>>b;

        if(prev == -1) prev = a;

        if(a != prev){
            // sort(klocki.begin(), klocki.end());

            vector<pair<int, int>> kol_size;
            while(!klocki.empty()){
                int curr = klocki.front();
                klocki.pop();
                int max_out = max(tree.get(0, curr-1), tree.get(curr+1, N-1));
                int wyn = max(max_out+prev-c, tree.get(curr, curr)+prev);

                kol_size.push_back({curr, wyn});
            }

            for(int i=0;i<kol_size.size();i++){
                tree.update(kol_size[i].first, kol_size[i].second);
            }

            prev = a;

        }
        klocki.push(b);
        
    }

    vector<pair<int, int>> kol_size;
    while(!klocki.empty()){
        int curr = klocki.front();
        klocki.pop();
        int max_out = max(tree.get(0, curr-1), tree.get(curr+1, N-1));
        int wyn = max(max_out+prev-c, tree.get(curr, curr)+prev);

        kol_size.push_back({curr, wyn});
    }

    for(int i=0;i<kol_size.size();i++){
        tree.update(kol_size[i].first, kol_size[i].second);
    }

    cout<<tree.get(0, N-1)<<endl;

    return 0;
}