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
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const LL Base = 5 * 1e5 + 7;
LL Pierdylion = 1e18 + 7;

LL n, c;
LL MaxKolor[Base];
LL LastHKolor[Base];
vector<pair<LL, LL>> Klocki;
LL Max = 0, TempMax = 0, pop = -1;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> c;
    LL a, b;
    for(int i = 0; i < Base; i++) LastHKolor[i] = Pierdylion;
    for(int i = 0; i < n; i++) {
        cin >> a >> b;
        Klocki.push_back({a, b});
    }
    reverse(Klocki.begin(), Klocki.end());
    // for(auto i : Klocki) {
    //     cerr << "(" << i.first << ", " << i.second << ")  ";
    // }
    // cerr << "\n";
    for(int i = 0; i < n; i++) {
        // cerr << Klocki[i].first << " " << Klocki[i].second << "  pop: " << pop << "  MaxKolor: " << MaxKolor[Klocki[i].second] << "\n";
        if(pop != Klocki[i].first) {
            Max = max(Max, TempMax);
            TempMax = 0;
            if(MaxKolor[Klocki[i].second] + Klocki[i].first >= Max - c + Klocki[i].first) {
                if(LastHKolor[Klocki[i].second] > Klocki[i].first) {
                    MaxKolor[Klocki[i].second] += Klocki[i].first;
                    LastHKolor[Klocki[i].second] = Klocki[i].first;
                }
                TempMax = max(TempMax, MaxKolor[Klocki[i].second]);
                if(MaxKolor[Klocki[i].second] < Max + Klocki[i].first - c) {
                    MaxKolor[Klocki[i].second] = Max + Klocki[i].first - c;
                    LastHKolor[Klocki[i].second] = Klocki[i].first;
                }
            } else {
                if(c > Klocki[i].first) {
                    if(LastHKolor[Klocki[i].second] > Klocki[i].first) {
                        MaxKolor[Klocki[i].second] += Klocki[i].first;
                        LastHKolor[Klocki[i].second] = Klocki[i].first;
                    }
                    if(MaxKolor[Klocki[i].second] < Max + Klocki[i].first - c) {
                        MaxKolor[Klocki[i].second] = Max + Klocki[i].first - c;
                        LastHKolor[Klocki[i].second] = Klocki[i].first;
                    }
                } else {
                    if(LastHKolor[Klocki[i].second] > Klocki[i].first) {
                        MaxKolor[Klocki[i].second] += Klocki[i].first;
                        LastHKolor[Klocki[i].second] = Klocki[i].first;
                    }
                    TempMax = max(TempMax, Max + Klocki[i].first - c);
                    if(MaxKolor[Klocki[i].second] < Max + Klocki[i].first - c) {
                        MaxKolor[Klocki[i].second] = Max + Klocki[i].first - c;
                        LastHKolor[Klocki[i].second] = Klocki[i].first;
                    }
                }
            }
        } else {
            if(MaxKolor[Klocki[i].second] + Klocki[i].first >= Max - c + Klocki[i].first) {
                if(LastHKolor[Klocki[i].second] > Klocki[i].first) {
                    MaxKolor[Klocki[i].second] += Klocki[i].first;
                    LastHKolor[Klocki[i].second] = Klocki[i].first;
                }
                TempMax = max(TempMax, MaxKolor[Klocki[i].second]);
                if(MaxKolor[Klocki[i].second] < Max + Klocki[i].first - c) {
                    MaxKolor[Klocki[i].second] = Max + Klocki[i].first - c;
                    LastHKolor[Klocki[i].second] = Klocki[i].first;
                }
            } else {
                if(c > Klocki[i].first) {
                    if(LastHKolor[Klocki[i].second] > Klocki[i].first) {
                        MaxKolor[Klocki[i].second] += Klocki[i].first;
                        LastHKolor[Klocki[i].second] = Klocki[i].first;
                    }
                    if(MaxKolor[Klocki[i].second] < Max + Klocki[i].first - c) {
                        MaxKolor[Klocki[i].second] = Max + Klocki[i].first - c;
                        LastHKolor[Klocki[i].second] = Klocki[i].first;
                    }
                } else {
                    if(LastHKolor[Klocki[i].second] > Klocki[i].first) {
                        MaxKolor[Klocki[i].second] += Klocki[i].first;
                        LastHKolor[Klocki[i].second] = Klocki[i].first;
                    }
                    TempMax = max(TempMax, Max + Klocki[i].first - c);
                    if(MaxKolor[Klocki[i].second] < Max + Klocki[i].first - c) {
                        MaxKolor[Klocki[i].second] = Max + Klocki[i].first - c;
                        LastHKolor[Klocki[i].second] = Klocki[i].first;
                    }
                }
            }
        }
        pop = Klocki[i].first;
    }
    Max = max(Max, TempMax);
    for(int i = 1; i < Base; i++) {
        Max = max(Max, MaxKolor[i]);
    }
    cout << Max;
}