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
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,l,r) for(int i = (l); i <= (r); i++)
#define FORD(i,l,r) for(int i = (l); i >= (r); i--)
using num = double;
using ind = long long;
struct bi{
    ind a;
    ind w;
};
ind t[500'001];
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ind n, c;
    cin >> n >> c;
    vector<bi> v;
    vector<vector<bi>> v2;
    FOR(i,1,n){
        ind a,w;
        cin >> a >> w;
        v.push_back({a,w});
    }
    sort(v.begin(),v.end(),[](bi a, bi b){
        return a.a > b.a;
    });
    ind preva=0;
    for(bi k : v){
        if(k.a != preva){
            preva = k.a;
            v2.push_back({});
        }
        v2.back().push_back(k);
    }
    ind maxwyn=0;
    for(vector<bi> v1 : v2){
        vector<bi> overwrites;
        ind new_max=maxwyn;
        for(bi k : v1){
            ind wyn = max(maxwyn + k.a - c, k.a + t[k.w]);
            overwrites.push_back({wyn,k.w});
            new_max = max(new_max, wyn);
        }
        maxwyn = max(maxwyn,new_max);
        for(bi k : overwrites){
            t[k.w] = max(t[k.w], k.a);
        }
    }
    FOR(i,1,500'000){
        maxwyn = max(maxwyn, t[i]);
    }
    cout << maxwyn << '\n';
}