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

#define f first
#define s second
using ll = long long;
using pll = pair<ll,ll>;

const int N = 5e5 + 5;

ll n, c;
pll w[N];
ll dp[N];
vector<pll> upds;
array<pll,4> mxs;
ll ans;

int main(){
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> c;

    for(int i=0;i<n;i++){
        cin >> w[i].f >> w[i].s;
    }

    sort(w,w+n,greater<pll>());

    int lst = -1;
    for(int i=0;i<n;i++){
        if(w[i].f != lst){
            for(auto p : upds){
                dp[p.s] = max(dp[p.s], p.f);
                bool f = false;
                for(int j=0;j<3;j++){
                    if(p.s == mxs[j].s){
                        mxs[j].f = max(mxs[j].f, p.f);
                        f = 1;
                    }
                }
                if(!f){
                    mxs[3] = p;
                    sort(mxs.begin(),mxs.end(),greater<pll>());
                }
            }
            upds.clear();
            lst = w[i].f;
        }
        ll val = 0;
        for(int j=0;j<3;j++){
            val = max(val, mxs[j].f - c * (w[i].s != mxs[j].s));
        }
        val = max(val, dp[w[i].s]);
        val += w[i].f;
        //cout << i << " " << w[i].f << " " << w[i].s << " " << val << " " << mxs[0].f << " " << mxs[0].s << " " << mxs[1].f << " " << mxs[1].s << " " << mxs[2].f << " " << mxs[2].s << "\n";
        upds.emplace_back(val, w[i].s);
        ans = max(ans, val);
    }

    cout << ans << "\n";
    
    return 0;
}