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
#include <cstdio>
#include <set>
#include <vector>
using namespace std;

const int KLOCEKLASSES = 500001;

struct klocek {
    int bigness;
    int kolor;
};

vector<klocek> klockis;

set<int> class_colors[KLOCEKLASSES];
long long best_results[500001];
long long best_overall = 0;
long long best_index = 0;
long long lowest_class = -1;

int main() {
    int n, c;
    scanf("%d %d", &n, &c);
    int a1, w1;
    scanf("%d %d", &a1, &w1);
    class_colors[a1].insert(w1);
    lowest_class = a1;

    for (int i = 1; i < n; ++i) {
        int a, w;
        scanf("%d %d", &a, &w);
        class_colors[a].insert(w);
    }
    for (int i = 1; i < 500001; ++i) {
        long long kara = c;
        if (i == lowest_class) {
            kara = 0;
        }
        long long potential_best_res = 0;
        long long potential_best_idx = 0;
        for (auto color: class_colors[i]) {
            long long match_result = best_results[color] + i;
            long long notch_result = best_overall + i - kara;
            long long highest = max(match_result, notch_result);
            if (highest > best_results[color]) {
                best_results[color] = highest;
                if (highest > potential_best_res) {
                    potential_best_res = highest;
                    potential_best_idx = color;
                }
            }
        }
        if (potential_best_res > best_overall) {
            best_overall = potential_best_res;
            best_index = potential_best_idx;
        }
    }

    printf("%lld\n", best_overall);
    return 0;
}