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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#ifndef TS_DEBUG
#define NDEBUG
#endif

#ifdef _WIN32
#include <io.h>
#include <fcntl.h>
#endif

#include <assert.h>
#include <iostream>
#include <stdint.h>

typedef int64_t i64;

const int MaxN = 500000;
const int MaxW = 500000;

int N;
int C;
int A[MaxN] = { 0 };
int W[MaxN] = { 0 };
i64 X[MaxN] = { 0 };
i64 XbyW[MaxW + 1] = { 0 };
i64 Xdowolny = 0;

void wczytaj()
{
    std::cin >> N >> C;
    for (int i = 0; i < N; i++) {
        int a, w;
        std::cin >> a >> w;
        A[i] = a;
        W[i] = w;
    }
}

void policz()
{
    int k = N;
    int j;
    while (k > 0) {
        i64 a = A[k - 1];

        j = k;
        while (j > 0 && A[j - 1] == a) { j--; }

        for (int i = j; i < k; i++) {
            i64 X1 = XbyW[W[i]] + a;
            i64 X2 = Xdowolny + a - C;
            X[i] = X1 >= X2 ? X1 : X2;
        }

        for (int i = j; i < k; i++) {
            XbyW[W[i]] = X[i];
            if (X[i] > Xdowolny) {
                Xdowolny = X[i];
            }
        }

        k = j;
    }
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

#ifdef _WIN32
    _setmode( _fileno( stdout ),  _O_BINARY );
#endif

    wczytaj();
    policz();

    i64 Wynik = Xdowolny;

    std::cout << Wynik << '\n';

    std::cout.flush();

    return 0;
}