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

struct xd{
    int a;
    int k;
};

xd klo[500007];
int wyn[500007];
queue <xd> q;

int32_t main()
{
    int n, m, i, j, a, b, k, c, ao=0, bo=0, w=0;
    xd m1={0, 0}, t;
    cin >> n >> c;
    for(i=0; i<n; i++){
        cin >> a >> b;
        if(a!=ao){
            while(!q.empty()){
                t=q.front();
                q.pop();
                wyn[t.k]=max(wyn[t.k], t.a);
                if(t.a>m1.a){
                    m1.a=t.a;
                    m1.k=t.k;
                }
            }
        }
        ao=a;
        k=wyn[b]+a;
        if(m1.k!=b){
            k=max(k, m1.a+a-c);
        }
        else{
            k=max(k, m1.a+a);
        }
        q.push({k, b});
    }
    while(!q.empty()){
        t=q.front();
        q.pop();
        wyn[t.k]=max(wyn[t.k], t.a);
        if(t.a>m1.a){
            m1.a=t.a;
            m1.k=t.k;
        }
    }
    for(i=0; i<=500000; i++){
        w=max(w, wyn[i]);
    }
    cout << w << '\n';
    return 0;
}