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
54
55
#include<bits/stdc++.h>

using namespace std;

const int maxn = 5e5 + 7;
const long long inf = 1e18;
vector<long long> score(maxn);
long long maxx = -inf;
long long maxx2 = -inf;
int maxxtyp;

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n,c; cin >> n >> c;
    vector<pair<int,int>> klocki(n);
    for(auto &[x,y] : klocki) cin >> x >> y;
    reverse(klocki.begin(), klocki.end());
    vector<pair<long long,int>> update;
    long long wynik = -inf;
    int i = 0;
    while(i < n){
        int j = i;
        int akt = klocki[i].first;
        while(j < n && klocki[j].first == akt){
            int typ = klocki[j].second;
            long long same = score[typ];
            long long different = -inf;
            if(maxxtyp != typ) different = maxx;
            else different = maxx2;
            if(different != -inf) different -= c;
            long long res = max({0LL, same, different}) + klocki[j].first;
            wynik = max(wynik, res);
            update.push_back({res, typ});
            j++;
        }
        for(auto [val, typ] : update){
            score[typ] = max(score[typ], val);
            if(maxx == -inf){
                maxx = val;
                maxxtyp = typ;
            }
            else{
                if(val > maxx){
                    maxx2 = maxx;
                    maxx = val;
                    maxxtyp = typ;
                }
                else if(val > maxx2) maxx2 = val;
            }
        }
        update.clear();
        i = j;
    }
    cout << wynik;
}