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
59
#include <bits/stdc++.h>
using namespace std;
const int SIZE=5e5+5;
const int base=1<<19;

long long tree[2*base];
int lastcol[SIZE];
int lastman[SIZE];
int colour[SIZE];
long long siz[SIZE];
long long dp[SIZE];

void ADD(int i,long long v){
    i+=base;
    while(i){tree[i]=max(tree[i],v);i/=2;}
}
long long QUERY(int a,int b){
    if(a>b){return 0;}
    long long MAX=0;
    a+=base-1;
    b+=base+1;
    while(a!=b-1){
        if(a%2==0){MAX=max(MAX,tree[a+1]);}
        if(b%2){MAX=max(MAX,tree[b-1]);}
        b/=2;
        a/=2;
    }
    return MAX;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long N,c;
    cin>>N>>c;

    for(int i=1;i<=N;i++){
        cin>>siz[i]>>colour[i];
    }

    for(int i=N;i>0;i--){

        if(lastcol[colour[i]]){
            if(siz[lastcol[colour[i]]]==siz[i]){lastman[i]=lastman[lastcol[colour[i]]];}
            else lastman[i]=lastcol[colour[i]];
        }
        lastcol[colour[i]]=i;



        dp[i]=max(QUERY(siz[i]+1,SIZE)-c+siz[i],dp[lastman[i]]+siz[i]);
        ADD(siz[i],dp[i]);

    }
    cout<<QUERY(1,SIZE);


return 0;}