CUBE-T193: Saengja

#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second
typedef long long lli;
typedef pair<int, int> pii;
typedef pair<int, lli> pil;

const int N = 1e5 + 5;

lli dp[N];
pii can[N];

int main(){

    int n, limWalk;
    scanf("%d%d", &n, &limWalk);
    for(int i = 1; i <= n; ++i){
        scanf("%d%d", &can[i].f, &can[i].s);
    }
    sort(can + 1, can + n + 1);
    deque<pil> dq;
    dp[0] = 0;
    for(int i = 1; i <= n; ++i){
        while(!dq.empty() && dq.front().f < can[i].f - limWalk){
            dq.pop_front();
        }
        dp[i] = dp[i - 1];
        if(!dq.empty()){
            dp[i] = max(dp[i], can[i].s - can[i].f + dq.front().s);
        }
        while(!dq.empty() && dq.back().s <= can[i].s + can[i].f + dp[i - 1]){
            dq.pop_back();
        }
        dq.emplace_back(can[i].f, can[i].s + can[i].f + dp[i - 1]);
    }
    cout << dp[n];

    return 0;
}