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
#include <iostream>
#include <map>
#include <set>
#include <vector>
using namespace std;
struct Wie {
  int c, last;
  map< long, set< int > > rescol;
  map< int, long > colres;
  vector< pair< int, long > > cache;
  Wie(int c = 0) : c(c), last(-1) {
    rescol[0].clear();
  }
  void update(int size, int color) {
    if (last != size) {
      flush();
      last = size;
    }
    map< long, set< int > >::iterator best = --rescol.end();
    long result = size;
    if (best->second.find(color) == best->second.end()) {
      result = max(result, best->first + size - c);
      map< int, long >::iterator it = colres.find(color);
      if (it != colres.end())
        result = max(result, it->second + size);
    } else
      result += best->first;
    cache.push_back(make_pair(color, result));
  }
  Wie &flush() {
    int i = cache.size();
    while (i--) {
      pair< int, long > &p = cache[i];
      map< int, long >::iterator it = colres.find(p.first);
      if (it != colres.end())
        rescol[it->second].erase(p.first);
      colres[p.first] = p.second;
      rescol[p.second].insert(p.first);
    }
    cache.clear();
    return *this;
  }
  long highest() const {
    return (--rescol.end())->first;
  }
};
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n, c, a, w;
  cin >> n >> c;
  Wie wie(c);
  while (n-- && cin >> a >> w)
    wie.update(a, w);
  cout << wie.flush().highest() << '\n';
}