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
#include <cstdio>
#define int long long

int kloa[500001] = {}, klow[500001] = {};
long long cp[500001] = {};
long long cplst[500001] = {};

signed main() {
    int n, c;
    scanf("%lld%lld", &n, &c);
    for (int i = 0; i < n; i++) scanf("%lld%lld", kloa+i, klow+i);
    kloa[n] = kloa[n-1];
    long long glm = 0;
    long long next_glm = 0;
    for (int i = n-1; i >= 0; i--) {
        if (kloa[i] != kloa[i+1]) {
            glm = next_glm;
        }
        if (cplst[klow[i]] == kloa[i]) continue;
        long long ncp = cp[klow[i]];
        if (ncp < glm - c) ncp = glm - c;
        ncp += kloa[i];
        cp[klow[i]] = ncp;
        cplst[klow[i]] = kloa[i];
        if (next_glm < ncp) next_glm = ncp;
    }
    printf("%lld", next_glm);
}