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
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <utility>
#include <map>
using namespace std;

typedef long long LL;

LL b = 0, b2 = 0;
int ba = -1;
vector<LL> z(501013);

void dodaj(int a, int w, LL x) {
    if (x > b) {
        if (a > ba) {
            b2 = b;
        }
        b = x;
        ba = a;
    }
    if (x > z[w]) {
        z[w] = x;
    }
}

int main() {
    int n, c;
    scanf("%d %d", &n, &c);
    vector<pair<int, int>> t(n);
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &t[i].first, &t[i].second);
    }
    sort(t.begin(), t.end());
    t.erase(unique(t.begin(), t.end()), t.end());
    n = t.size();
    for (int i = 0; i < n; i++) {
        int a = t[i].first, w = t[i].second;
        dodaj(a, w, z[w]+a);
        if (ba < a) dodaj(a, w, b+a-c);
        else dodaj(a, w, b2+a-c);
    }
    printf("%lld\n", b);
	return 0;
}