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
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000009
#define INF 1000000019
#define INFL 1000000000000000099LL

ll n,c,a,b;
vector<pair<ll,ll>>kloc;
ll dp[500007];
ll bst;

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>c;
    for(ll i=0;i<n;i++){
        cin>>a>>b;
        kloc.pb({a,b});
    }
    sort(kloc.begin(),kloc.end());
    kloc.pb({INF,-1});
    reverse(kloc.begin(),kloc.end());
    kloc.pb({-1,-1});
    vector<ll>ak;
    for(ll i=1;i<kloc.size();i++){
        if(kloc[i].ff==kloc[i-1].ff)
            ak.pb(kloc[i].ss);
        else{
            vector<pair<ll,ll>>pom;//<kolor,wynikpotencjalny>
            for(ll j : ak){
                pom.pb({j,kloc[i-1].ff+max(dp[j],bst-c)});
            }
            for(pair<ll,ll> j :pom){
                bst=max(bst,j.ss);
                dp[j.ff]=max(dp[j.ff],j.ss);
            }
            ak.clear();
            ak.pb(kloc[i].ss);
        }
    }
    cout<<bst;
    return 0;
}