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
#include <bits/stdc++.h>
using namespace std;

#define int _ll
using _ll = long long;

#define loop(i, a, b) for(int i = a; i <= b; i++)
#define loop_rev(i, a, b) for(int i = a; i >= b; i--)
#define all(x) x.begin(), x.end()
#define sz(x) int(x.size())
#define eb emplace_back
#define pb push_back

struct SegTree {
  int TREE_BASE = 1;
  vector<int> tree;
  void resize(int n) {
    while(TREE_BASE < n) TREE_BASE *= 2;
    tree.resize(2 * TREE_BASE);
  }
  int query(int a, int b) {
    a += TREE_BASE;
    b += TREE_BASE + 1;
    int res = 0;
    while(a < b) {
      if(a & 1) res = max(res, tree[a++]);
      if(b & 1) res = max(res, tree[--b]);
      a /= 2, b /= 2;
    }
    return res;
  }
  void update(int i, int val) {
    i += TREE_BASE;
    while(i) {
      tree[i] = max(tree[i], val);
      i /= 2;
    }
  }
};

signed main() {
  cin.tie(0)->sync_with_stdio(0);
  int n, c; cin >> n >> c;

  vector<int> a(n + 2), w(n + 2);
  int max_w = 0;

  loop(i, 1, n) {
    cin >> a[i] >> w[i];
    max_w = max(max_w, w[i]);
  }

  SegTree dp;
  dp.resize(max_w + 2);
  int ind = 1, res = 0;

  while(ind <= n) {
    vector<pair<int, int>> pending;
    do {
      pending.pb({
        w[ind],
        max({
          dp.query(w[ind], w[ind]) + a[ind],
          dp.query(0, w[ind] - 1) + a[ind] - c,
          dp.query(w[ind] + 1, max_w + 1) + a[ind] - c
        })
      });
      ++ind;
    } while(a[ind] == a[ind - 1]);
    for(auto [ x, val ] : pending) {
      res = max(res, val);
      dp.update(x, val);
    }
  }

  cout << res << '\n';

}