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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
#define int long long
using namespace std;

int32_t main() 
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int bmn = -1000000000000000000LL;
    int lic, kar;
    cin >> lic >> kar;

    vector<int> bok(lic), wzo(lic), ocn(lic);

            for (int klo = 0; klo < lic; klo++) 
            {
                cin >> bok[klo] >> wzo[klo];
            }

        unordered_map<int, int> pam;
        pam.reserve(lic);
        pam.max_load_factor(0.7f);

    int ogb = bmn, wyn = 0;
    int klo = 0;

            while (klo < lic) 
                {
                int wym = bok[klo];
                vector<int> gru;

                    while (klo < lic && bok[klo] == wym) 
                    {
                        gru.push_back(klo);
                        klo++;
                    }

                        for (int pst : gru) 
                            {
                            int a = bok[pst];
                            int w = wzo[pst];
                            auto it = pam.find(w);
                            int x = (it == pam.end() ? bmn : it->second);
                            int val = a + max({0LL, x, ogb - kar});
                            ocn[pst] = val;
                            wyn = max(wyn, val);
                        }

                    for (int pst : gru) 
                        {
                        int v = ocn[pst];
                        ogb = max(ogb, v);
                        int w = wzo[pst];
                        auto it = pam.find(w);
                                if (it == pam.end() || it->second < v)
                                 {
                                    pam[w] = v;
                                }
                    }
            }

    cout << wyn;
    return 0;
}