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

using namespace std;

typedef long long ll;

set<pair<ll, ll>> ks;
unordered_map<ll, ll> bests;

int main() {
    ll n, c;
    cin >> n >> c;

    for(ll i = 0; i < n; i++) {
        ll a, w;
        cin >> a >> w;

        ks.insert({a, w});
    }

    vector<pair<ll, ll>> ksv(ks.begin(), ks.end());
    sort(ksv.begin(), ksv.end());
    reverse(ksv.begin(), ksv.end());

    ll best = 0;
    ll i = 0;
    while(i < ksv.size()) {
        ll ba = ksv[i].first;

        ll best_tmp = best;
        while(i < ksv.size() && ksv[i].first == ba) {
            ll a = ksv[i].first;
            ll w = ksv[i].second;

            bests[w] = max(best + a - c, bests[w] + a);
            best_tmp = max(bests[w], best_tmp);
            best_tmp = max(best_tmp, best + a - c);

            i++;
        }

        best = max(best, best_tmp);
    }

    cout << best << "\n";

    return 0;
}