https://www.luogu.com.cn/problem/P3957
https://class.51nod.com/Html/Textbook/ChapterIndex.html#textbookId=126&chapterId=337
显然，但是维护滑动窗口有技巧，不能每次插入一个值，因为维护 \(x\) 不方便。
所以考虑一个 \(cur\)，每次对于新的 \(i\) 不能跳过时移动 \(cur\)，然后队首无法到达出队，最后再取值。
请注意，初始化成 \(-INF\)，保证不会从不合法的位置跳过来，否则50pts。
#include<iostream>
#include<cstring>
typedef long long ll;
using namespace std;
const int N=500010;
int n,d,k,x[N],s[N],q[N];
ll f[N];
void read(int &x){
x=0;
bool f=0;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f=1;
c=getchar();}
while(isdigit(c))x=x*10+c-'0',c=getchar();
if(f)x=-x;
}
bool check(int g){
ll ans=0;
memset(f+1,-0x3f,n*8);
int hh=0,tt=-1,l=max(d-g,1),r=d+g,cur=0;
for(int i=1;i<=n;++i){
while(cur<i&&x[cur]+l<=x[i]){
while(hh<=tt&&f[q[tt]]<=f[cur])--tt;
q[++tt]=cur;
++cur;
}
while(hh<=tt&&x[q[hh]]+r<x[i])++hh;
if(hh<=tt)f[i]=f[q[hh]]+s[i];
// printf("f[%d]=%d\n",i,f[i]);
ans=max(ans,f[i]);
}
return ans>=k;
}
int main(){
#ifdef LOCAL
freopen("1.txt","r",stdin);
#endif
#ifndef LOCAL
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
#endif
read(n);
read(d);
read(k);
ll tot=0;
for(int i=1;i<=n;++i)read(x[i]),read(s[i]),tot+=s[i]>0?s[i]:0;
if(tot<k)return cout<<"-1\n",0;
int l=0,r=1e9;
while(l<r){
int mid=l+r>>1;
if(check(mid))r=mid;
else l=mid+1;
}
cout<<r;
// cout<<check(2);
return 0;
}