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
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC optimize("O0")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
#pragma GCC optimize("unroll-loops")

using namespace std;
//using namespace __gnu_pbds;

#define pb push_back
#define F first
#define S second
#define ll long long
#define ld double long
#define ull unsigned long long
#define endl '\n'


const ll N = 5e5 + 36;
const ll M = 1e2 + 36;
const ll INF = 1e9 + 7;
const ll MOD = 1e9 + 7;
const ll MOD1 = 888888901;
const ll MOD2 = 999988901;
const ll X[8] = {1, -1, 2, 2, -2, -2, 1, -1};
const ll Y[8] = {2, 2, 1, -1, 1, -1, -2, -2};
const ld PI = 3.14159265358979323846;
const ld EPS = 1e-10;

//tree < pair < string, int >, null_type, less < pair < string, int > >, rb_tree_tag, tree_order_statistics_node_update > a;

//mt19937 gen(chrono::system_clock::now().time_since_epoch().count());
mt19937 gen(19937);

signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
#endif // LOCAL
    ll n, c;
    cin >> n >> c;
    vector<pair<ll,ll>> a(n);
    for (int i(0); i < n; ++i) {
        cin >> a[i].F >> a[i].S;
    }
    sort(a.begin(), a.end());
    vector<vector<pair<int, pair<ll,ll>>>> kek;

    int lst = 0;
    for (int i(0); i < n; ++i) {
        if (lst != a[i].F) {
            kek.pb({});
            lst = a[i].F;
        }
        kek.back().pb({i, a[i]});
    }

    vector<ll> dp(n, 0);
    vector<pair<ll, int>> col(N, {-1, -1});
    ll ans = 0;

    ll i = 0, best_prev = 0;
    for (auto to:kek) {

        for (auto go:to) {
            dp[go.F] = go.S.F;
            dp[go.F] = max(dp[go.F], best_prev + go.S.F - c);
            if (col[go.S.S].S != -1) {
                dp[go.F] = max(dp[go.F], go.S.F + dp[col[go.S.S].S]);
            }
            ans = max(ans, dp[go.F]);
        }

        for (auto go:to) {
            col[go.S.S] = max(col[go.S.S], {dp[go.F], go.F});
        }

        best_prev = ans;
    }


    /*for (int i(0); i < n; ++i) {
        dp[i] = a[i].F;
        if (i) {
            dp[i] = max(dp[i], dp[i - 1] + a[i].F - c);
        }
        if (col[a[i].S] != -1) {
            dp[i] = max(dp[i], a[i].F + dp[col[a[i].S]]);
        }
        col[a[i].S] = i;
        ans = max(ans, dp[i]);
    }*/

    cout << ans << endl;
    return 0;
}