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

struct block {int a; int w;};

block T[500000];
int   A[500001];
long  G[500001];
long  H[500001];

int main()
{
  int n, c;
  scanf("%i %i ", &n, &c);
  for (int i = 0; i<n; i++) scanf("%i %i ", &T[i].a, &T[i].w), A[T[i].w] = G[T[i].w] = H[T[i].w] = 0;
  A[0] = G[0] = H[0] = 0;
  sort(T, T+n, [&](block a, block b){return a.a<b.a;});
  for (int i = 0; i<n; i++)
  {
    int a = T[i].a, w = T[i].w;
    if (a>A[w]) A[w] = a, G[w] = H[w];
    if (a>A[0]) A[0] = a, G[0] = H[0];
    H[w] = max(G[w], G[0]-c)+a;
    H[0] = max(H[0], H[w]);
  }
  printf("%li\n", H[0]);
  return 0;
}