https://www.luogu.com.cn/record/113549238

#include<bits/stdc++.h>
using namespace std;
const long long inf=~0x3f3f3f3f3f3f3f3f;
int p[500010],q[500010]; long long dp[500010];
bool check(int g,int n,int d,int k){
    memset(dp,inf,sizeof(dp)); dp[0]=0;
    int s=max(1,d-g),t=d+g,pos=0; deque<int>dq;
    long long ans=inf; for(int i=1;i<=n;i++){
        while(p[i]-p[pos]>=s&&pos<i){
            if(dp[pos]!=inf){
                while(!dq.empty()&&dp[dq.front()]<=dp[pos]) 
                    dq.pop_back(); dq.push_back(pos);
            } pos++;
        }
        while(!dq.empty()&&p[i]-p[dq.front()]>t) dq.pop_front();
        if(!dq.empty()) dp[i]=dp[dq.front()]+q[i];
        if(dp[i]!=inf) ans=max(ans,dp[i]);
    } return ans>=k;
}
int main(){
    int n,d,k;scanf("%d%d%d",&n,&d,&k);
    for(int i=1;i<=n;i++) scanf("%d%d",&p[i],&q[i]);
    int l=0,r=1e9,ans=-1;
    while(l<=r){
        int mid=l+r>>1;
        if(check(mid,n,d,k)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    printf("%d",ans); return 0;
}