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
//PROBLEM 4C
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
int main() {
    #define int long long
    int n, c;
    cin >> n >> c;
    vector<array<int, 2>> r(n);
    map<int, set<int>> vals;
    for(auto &[a, w] : r) {
        cin >> a >> w;
        vals[a].insert(w);
    }
    array<int, 2> best{1, -1};
    map<int, int> best_col;
    for(auto [a, Ws] : vals) {
        vector<array<int, 2>> local;
        for(auto w : Ws) {
            int me = best[0] + a - c*(best[1] != w);
            me = max(me, best_col[w] + a);
            // cout << a << " " << w << " "<< best_col[w] << endl;
            local.push_back({me, w});
            // best_col[w] = me;
            // best = max(best, {me, w});
        }
        for(auto v : local) {
            best = max(best, v);
            best_col[v[1]] = v[0];
        }
    }
    cout << best[0] << '\n';
}