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
#include <cstdio>
#include <vector>

using namespace std;

#define MAX 500100

typedef long long ll;

ll n,c,a,w;

ll best_w[MAX];
vector<pair<int,ll>> curr;
ll r_b = 0;

void add() {
    for(int i=0;i<curr.size();i++)  {
        if(best_w[curr[i].first] < curr[i].second) best_w[curr[i].first] = curr[i].second;
        if (r_b < curr[i].second) r_b = curr[i].second;
    }
    curr.clear();
}

int main() {
    scanf("%lld %lld", &n, &c);

    int c_a = 0;
    for(int j=0;j<n;j++) {
        scanf("%lld %lld", &a, &w);
        if (c_a != a) {
            add();
            c_a = a;
        }
        curr.emplace_back(w, r_b + a - c);
        curr.emplace_back(w, best_w[w] + a);
    }
    add();

    printf("%lld\n", r_b);
}