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
#include <bits/stdc++.h>
using namespace std;
const int MX=500500;
int n,c;
long long f[MX];
pair<int,int> a[MX];
map<int, long long> lst;
int main() {
  scanf("%d%d",&n,&c);
  for (int i=0; i<n; i++) scanf("%d%d",&a[i].first,&a[i].second);
  sort(a,a+n);
  reverse(a,a+n);
  long long best=0;
  for (int i=0, j=0; i<n; i=j) {
    for (j=i; j<n && a[i].first==a[j].first; j++) {
      auto it=lst.find(a[j].second);
      f[j]=(it!=lst.end())?it->second:0;
      f[j]=max(f[j],best-c)+a[j].first;
    }
    for (int k=i; k<j; k++) {
      lst[a[k].second]=f[k];
      best=max(best,f[k]);
    }
  }
  printf("%lld\n",best);
  return 0;
}