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
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i = a; i < b;++i)
#define pb push_back
#define pi pair<int,int>
#define f first
#define s second
#define int long long
using namespace std;
const int maxn = 500 * 1000 + 5;
int wyn[maxn];
int32_t main(){
    int n,c;
    cin>>n >>c;
    vector<pi> V,ost;
    FOR(i,0,n){
        int a,w;
        cin>>a >>w;
        V.pb({a,w});
    }
    reverse(V.begin(),V.end());
    int maks = 0;
    FOR(i,0,V.size()){
        if(i != 0 && V[i].f != V[i - 1].f){
            for(auto y : ost){
                wyn[y.f] = max(wyn[y.f],y.s);
                maks = max(maks,y.s);
            }   
            ost.clear();
        }
        int x = max(maks - c,wyn[V[i].s]) + V[i].f;
        ost.pb({V[i].s,x});
    }
    for(auto y : ost){
        wyn[y.f] = max(wyn[y.f],y.s);
        maks = max(maks,y.s);
    }
    cout<<maks;
}