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>

#define ll long long
#define ve vector
#define fi first
#define se second
#define ld double
#define all(x) x.begin(), x.end()

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 5e5+10;

ve<int> cols[MAXN];
int lst[MAXN];
map<int, ll> dp[MAXN];
ll mxdp[MAXN];

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, c;
    cin >> n >> c;
    for(int i = 0; i < n; i++){
        int a, b;
        cin >> a >> b;
        cols[a].push_back(b);
    }
    for(int i = 1; i < MAXN; i++){
        mxdp[i] = mxdp[i - 1];
        for(auto col : cols[i]){
            dp[i][col] = max({dp[i][col], mxdp[i - 1] + i - c, i + dp[lst[col]][col]});
            mxdp[i] = max(mxdp[i], dp[i][col]);
            
        }
        for(auto col : cols[i])
            lst[col] = i;
    }
    cout << mxdp[MAXN - 1]<< "\n";
}