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
#include<bits/stdc++.h>
#define st first
#define nd second
#define all(x) x.begin(), x.end()
#define BOOST cin.tie(NULL); ios_base::sync_with_stdio(false);
 
// #define int ll
typedef long long ll;

using namespace std;
template <typename T> struct tag:reference_wrapper <T>{ using reference_wrapper <T>::reference_wrapper; };
template <typename T1, typename T2> static inline tag <ostream> operator<<(tag <ostream> os, pair<T1, T2> const& p){ return os.get()<<"{"<<p.first<<", "<<p.second<<"}", os;}
template <typename Other> static inline tag <ostream> operator<<(tag <ostream> os, Other const& o){ os.get()<<o; return os; }
template <typename T> static inline tag <ostream> operator <<(tag <ostream> os, vector <T> const& v){ os.get()<<"["; for (int i=0; i<v.size(); i++) if (i!=v.size()-1) os.get()<<v[i]<<", "; else os.get()<<v[i]; return os.get()<<"]", os; }
template <typename T> static inline tag <ostream> operator <<(tag <ostream> os, set <T> const& s){ vector <T> v; for (auto i: s) v.push_back(i); os.get()<<"["; for (int i=0; i<v.size(); i++) if (i!=v.size()-1) os.get()<<v[i]<<", "; else os.get()<<v[i]; return os.get()<<"]", os; }



int32_t main(){
    BOOST;
    int n, c; cin >> n >> c;
    vector<pair<int,int>> blk(n);
    for(int i = 0; i < n; i++){
        cin >> blk[i].first >> blk[i].second;
    }
    sort(all(blk), greater<pair<int,int>>());
    blk.resize(distance(blk.begin(), unique(all(blk))));
    n = blk.size();
    // cout << blk << "\n";

    vector<long long> dp(n, 0);
    vector<long long> maxw(500010, 0);
    int last_base = 1e9;
    long long last_maxh = 0;
    int curr_base = blk[0].first;
    long long curr_maxh = 0;
    for(int i = 0; i < n; i++){
        if(curr_base == blk[i].first){
            dp[i] = max(maxw[blk[i].second] + blk[i].first, last_maxh + blk[i].first - c);
            curr_maxh = max(curr_maxh, dp[i]);
            maxw[blk[i].second] = max(maxw[blk[i].second], dp[i]);
        } else {
            last_maxh = curr_maxh;
            curr_base = blk[i].first;
            i--;
        }
    }
    cout << curr_maxh << "\n";
    return 0;
}