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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
set<pair<ll,ll>> s;

map<ll,ll> poprz;
map<ll,ll> curr;
ll wyn = 0;
ll prevmax = 0;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n, c;
    cin >> n >> c;
    ll a, b;
    for(int i = 0; i < n; ++i){
        cin >> a >> b;
        s.insert({a,b});
    }
    vector<pair<ll,ll>> v;
    for(auto u : s){
        v.push_back(u);
    }
    reverse(v.begin(),v.end());
    ll it = 0;
    while(it < v.size()){
        ll a = v[it].first;
        while(it < v.size() and v[it].first == a){
            curr[v[it].second] = max({v[it].first, poprz[v[it].second] + v[it].first, prevmax + v[it].first - c});
            ++it;
        }
        for(auto u : curr){
            prevmax = max(prevmax, u.second);
            poprz[u.first] = max(u.second,poprz[u.first]);
            wyn = max(wyn, prevmax);
        }
        curr.clear();
    }
    cout << wyn << "\n";
    return 0;
}