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
#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<pair<int,int>> v;
const int maxn = 500009;
int dp[maxn];
int dp2[maxn];
int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,c;
    cin >> n >> c;
    for(int i = 0; i<n; i++){
        int a,b;
        cin >> a >> b;
        v.emplace_back(a,b);
    }
    sort(v.begin(), v.end(), greater<pair<int,int>>());
    int ans = 0;
    int i = 0;
    while(i < n){
        int indx = i;
        int old_i = i;
        while(indx < n and v[indx].first == v[i].first){
            dp2[v[indx].second] = max(dp2[v[indx].second], max(dp[v[indx].second] + v[indx].first, ans + v[indx].first - c));
            indx++;
        }
        for(int x = old_i; x< indx; x++){
            dp[v[x].second] = max(dp[v[x].second], dp2[v[x].second]);
            ans = max(ans,dp[v[x].second]);
        }
        for(int x = old_i; x< indx; x++){
            dp2[v[x].second] = 0;
        }
        i = indx;
    }
    cout << ans << "\n";
}