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
#include "bits/stdc++.h"

#define int long long
#define pi pair<long long, long long>
#define a3 array<long long, 3>

#define meow main

using namespace std;

struct tree {
  vector<pi> T;
  int L = 1;
  tree(int n) {
    L = 1;
    while (L <= n)
      L *= 2;
    T.resize(2 * L);
    for (int i = L; i < 2 * L; i++)
      T[i] = {INT_MIN, i - L};
  }

  pi query(int p, int q) {
    if (p >= q)
      return {INT_MIN, -1};
    p += L;
    q += L;
    pi res = T[p];
    while (p / 2 != q / 2) {
      if (p % 2 == 0)
        res = max(res, T[p + 1]);
      if (q % 2 == 1)
        res = max(res, T[q - 1]);

      p /= 2;
      q /= 2;
    }
    return res;
  }

  void update(int p, int val) {
    int ind = p;
    p += L;
    while (p) {
      T[p] = max(T[p], {val, ind});
      p /= 2;
    }
  }
};

signed meow() {
  cin.tie((ostream *)!ios::sync_with_stdio(false));

  int n, c;
  cin >> n >> c;
  vector<vector<int>> klocki(500001);
  while (n--) {
    int a, b;
    cin >> a >> b;
    klocki[a].push_back(b);
  }

  tree T(500002);
  for (int rozmiar = 0; rozmiar < 500001; rozmiar++){
    vector<pi> to_update;
    for (auto kolor : klocki[rozmiar]) {
      int res = rozmiar;
      auto [val, ind] = T.query(0, 500001);
      res = max(res, val + rozmiar - c);
      auto [kval, trash] = T.query(kolor, kolor + 1);
      res = max(res, kval + rozmiar);

      to_update.push_back({kolor, res});
    }
    for(auto [kolor, res] : to_update) {
      T.update(kolor, res);
    }
  }

  cout << T.query(0, 500001).first << '\n';

  return 0;
}