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
#include <bits/stdc++.h>
using namespace std;

constexpr int MAX_N = 5e5;

int n, c, a, w;

map<int, vector<int>, greater<int>> klocki;

map<int, long long> max_w;
long long max_all;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> c;

    for(int i = 1; i <= n; i++) {
        cin >> a >> w;
        klocki[a].push_back(w);
    }

    for(auto i : klocki) {
        vector<pair<int, long long>> current;

        for(int j : i.second) {
            current.push_back({j, max(max_all - c, max_w[j]) + i.first});
        }

        for(auto j : current) {
            max_w[j.first] = max(max_w[j.first], j.second);
            max_all = max(max_all, j.second);
        }
    }

    cout << max_all;
}