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
#include<bits/stdc++.h>
#define ll long long
using namespace std;

const ll INF = -1e18;
bool compare(pair<ll, ll> a, pair<ll, ll> b){
    if(a.first != b.first) return a.first > b.first;
    return a.second < b.second;
}
 
int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    
    ll n, c;
    cin >> n >> c;
    vector<pair<ll, ll>> v(n);
    for(ll i = 0; i < n; i++) cin >> v[i].first >> v[i].second;
    sort(v.begin(), v.end(), compare);
    vector<ll> najwzor(500007, INF);
    ll pierwszy = INF;
    ll drugi = INF;
    ll wzor = -1;
    ll wynik = 0;

    for(ll i = 0; i < n; i++){
        ll j = i;
        vector<pair<ll,ll>> vec;
        while(j < n and v[j].first == v[i].first){
            ll diff;
            if(pierwszy == INF) diff = INF;
            else{
                if(wzor != v[j].second) diff = pierwszy;
                else diff = drugi;
                if(diff != INF) diff -= c;
            }
            ll dp = max(0LL, max(najwzor[v[j].second], diff)) + v[j].first;
            vec.push_back({v[j].second, dp});
            wynik = max(wynik, dp);
            j++;
        }
        for(auto x : vec){
            najwzor[x.first] = max(najwzor[x.first], x.second);
            if(x.second > pierwszy){
                if(wzor == x.first) pierwszy = x.second;
                else{
                    drugi = pierwszy;
                    pierwszy = x.second;
                    wzor = x.first;
                }
            }
            else if(x.first != wzor and x.second > drugi) drugi = x.second;
            else if(x.second == pierwszy and x.first != wzor) drugi = pierwszy;
        }
        i = j;
        i--;
    }
    cout << wynik;
}