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
#include <algorithm>
#include <cstdio>
#include <map>
#include <set>
#include <tuple>
#include <vector>

using namespace std;

const int MAX_SIZE = 500001;
using value_type = long long;

set<int> patterns_at_size[MAX_SIZE];

template <typename T> void print_vector(vector<T> v) {
  for (int i = 0; i < v.size(); i++) {
    printf("%lld ", v[i]);
  }

  puts("");
}

int main() {
  int n, c;

  scanf("%d %d", &n, &c);

  for (int i = 0; i < n; i++) {
    int a, w;

    scanf("%d %d", &a, &w);

    patterns_at_size[a].insert(w);
  }

  map<int, value_type> best_tower_at_color;
  value_type best_current_tower = 0;

  for (int i=MAX_SIZE - 1; i>=0; i--) {
    value_type best_this_iteration = best_current_tower;

    for (auto &pattern : patterns_at_size[i]) {
      best_tower_at_color[pattern] = max(best_tower_at_color[pattern] + i, best_current_tower - c + i);
      best_this_iteration = max(best_this_iteration, best_tower_at_color[pattern]);
    }

    best_current_tower = max(best_this_iteration, best_current_tower);
  }

  // for (auto [k, v] : best_tower_at_color) {
  //   printf("p: %d, v: %d\n", k, v);
  // }

  printf("%lld", best_current_tower);

  return 0;
}