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
99
#include <bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define fr(i,n) for(int i=0; i<(n); i++)
#define frx(i,a,b) for(int i=(a); i<=(b); i++)
#define ok(cond) cout << ((cond) ? "Yes" : "No") << "\n";
#define watch(x) cerr << (#x) << " == " << (x) << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef const int ci;
typedef const ll cll;
typedef const ld cld;
typedef pair<int,int> pii;
typedef set<int> si;
typedef vector<int> vi;
typedef vector<pair<int,int>> vpii;
typedef vector<pair<int,ll>> vpill;


template<typename T1, typename T2>
istream& operator>>(istream& is, pair<T1,T2>& p) {
    return is >> p.st >> p.nd;
}

template<typename T1, typename T2>
ostream& operator<<(ostream& os, pair<T1,T2>& p) {
    return os << p.st << " " << p.nd;
}


template<typename T>
ostream& operator<<(ostream& os, vector<T>& v) {
    for (T x : v) {
        os << x << " ";
    }
    return os;
}

template<typename T>
ostream& operator<<(ostream& os, set<T>& s) {
    for (T x : s) {
        os << x << " ";
    }
    return os;
}

const int N = 5e5;
ll a[N+5], w[N+5];
priority_queue<pair<ll,int>> best_towers;
vector<pair<ll,int>> updated_towers;
ll pattern_tower[N+5];

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

    int n;
    ll c;
    cin>>n>>c;

    fr(i,n){
        cin>>a[i]>>w[i];
        best_towers.push({0, w[i]});
    }
    a[n] = 0;
    best_towers.push({0, 0});

    fr(i,n) {
        pair<ll,int> best = best_towers.top();
        best_towers.pop();
        while (best_towers.top().nd == best.nd) {
            best_towers.pop();
        }

        ll same_patt = pattern_tower[w[i]];
        ll diff_patt = (best.nd == w[i]) ? best_towers.top().st : best.st;

        best_towers.push(best);
        updated_towers.pb({max(same_patt+a[i], diff_patt+a[i]-c), w[i]});

        if (a[i] != a[i+1]) {
            while (!updated_towers.empty()) {
                pair<ll,int> updated = updated_towers.back();
                best_towers.push(updated);
                pattern_tower[updated.nd] = max(pattern_tower[updated.nd], updated.st);
                updated_towers.pop_back();
            }
        }
    }

    cout << best_towers.top().st << "\n";

    return 0;
}