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

vector < pii > v;
const int t = 500'003;
ll last[t];
ll dp[t];
set < pii > mapa;

int main(){
    ll n, c;
    cin >> n >> c;
    for(int i = 0; i < n; i++){
        ll a, b;
        cin >> a >> b;
        if(mapa.find({a, b}) == mapa.end()) v.push_back({a, b});
        mapa.insert({a, b});
    }
    sort(v.begin(), v.end(), greater < pii > ());
    ll ma = 0, sma = 0, najw = 0;
    bool cos = 0;
    for(int i = 0; i < v.size(); i++){
        if(i >= 1 && v[i].first < v[i - 1].first){
            cos = 1;
            for(int j = sma; j < i; j++){
                najw = max(najw, dp[j + 1]);
            }
            sma = i;
        }
        if(last[v[i].second] == 0){
            dp[i + 1] = najw + v[i].first - c;
            if(!cos) dp[i + 1] += c;
        }
        else {
            dp[i + 1] = max(najw - c, dp[last[v[i].second]]) + v[i].first;
        }
        last[v[i].second] = i + 1;
        ma = max(ma, dp[i + 1]);
    }
    cout << ma << "\n";
}