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

typedef pair<long long, long long> par;
priority_queue<par> q;
vector<par> temp;
vector<int> v[500009];
long long cost[500009];


int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    long long n, c, a, b, d, wyn = 0;
    par p, p0;
    cin>>n>>c;
    q.push(par(0, 0));
    for(int i=1; i<=n; i++) {
        cin>>a>>b;
        v[a].push_back(b);
    }
    for(int i=500000; i>=1; i--) {
        if(v[i].size() == 0) continue;
        temp.clear();
        for(int j=0; j<v[i].size(); j++) {
            a = i;
            b = v[i][j];
            p = q.top();
            if(p.second == b) {
                p0 = p;
                q.pop();
                p = q.top();
            }
            else p0 = par(-1, -1);
            d = cost[b] + a;
            if(p.first + a - c > d) d = p.first + a - c;
            temp.push_back(par(d, b));
            if(p0.first != -1) q.push(p0);
        }
        for(int j=0; j<temp.size(); j++) {
            p = temp[j];
            cost[p.second] = p.first;
            if(p.first > wyn) wyn = p.first;
            q.push(p);
        }
    }
    cout<<wyn;
    return 0;
}