我们充分发挥人类智慧，发现太远的格子一定跳不到目前的格子，于是暴力并搜每个格子前7个，这样在 $n\le5\times10^5$ 时也可以卡过（甚至在最优解第16页）

神金AC记录

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define ci const int
#define us unsigned
#define int long long
#ifdef ONLINE_JUDGE
#define getchar getchar_unlocked
#endif
int re();
struct gg{
	int x,v;
	gg(){x=v=0;}
	gg(ci a,ci b){x=a,v=b;}
	bool operator<(const gg a)const{return x<a.x;}
}a[500050];
int n,d,k,all,mx;
int dp[500050];
bool can_jump(ci st,ci ed,ci l,ci r){
	return l<=ed-st&&ed-st<=r;
}
bool luangao(ci co){
	memset(dp,168,sizeof dp);
	dp[0]=0;
	for(int i=1;i<=n;++i){
		ci qww=std::lower_bound(a,a+i,gg(a[i].x-d-co,a[i].v))-a;
		for(int j=(qww>i-7?qww:i-7);j<i;++j)
			if(can_jump(a[j].x,a[i].x,(d>co?d-co:1),d+co))
				dp[i]=(dp[i]<dp[j]+a[i].v?dp[j]+a[i].v:dp[i]);
			else break;
		if(dp[i]>=k)return 1;
	}return 0;
}
bool chk(ci co){
	return luangao(co);
}
signed main(){
	n=re(),d=re(),k=re();
	for(int i=1,x,y;i<=n;++i)
		x=re(),y=re(),a[i]=gg(x,y),(y>0?all+=y:0);
	if(all<k)return puts("-1"),0;
	all=0;
	while(a[n].v<0)--n;
	int L=0,R=(a[n].x>d?a[n].x:d),mid,ans=R;
	while(L<=R){
		mid=L+R>>1;
		if(chk(mid))R=mid-1,ans=mid;
		else L=mid+1;
	}printf("%lld",ans);
	return 0;
}
int re(){
	int x=0;char c=getchar(),f=0;
	while(c<48||c>57)f|=(c=='-'),c=getchar();
	while(c<58&&c>47)x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return f?-x:x;
}