WA on #3,4,5,9,10

#include<bits/stdc++.h>
using namespace std;
const int N=500005;
long long n,d,k,x[N],y[N],dp[N],q[N],sum,l,r=1e9,mid,id,minn,maxn,ans;
bool check(long long num){
	ans=0,minn=max(1ll,d-num),maxn=d+num,id=0;
	long long l=1,r=0;
	for(int i=1;i<=n;i++) dp[i]=-1e13;
	for(int i=1;i<=n;i++){
		while(x[i]-x[id]>=minn&&x[i]-x[id]<=maxn){
			while(l<=r&&x[i]-x[q[l]]>maxn) l++;
			while(l<=r&&dp[id]>=dp[q[r]]) r--;
			q[++r]=id++;
		}
		if(l==1&&r==0) continue;
		dp[i]=dp[q[l]]+y[i];
		ans=max(ans,dp[i]);
	}
	if(ans>=k) return true;
	return false;
}
int main(){
	//freopen("P3957_3.in","r",stdin);
	cin>>n>>d>>k;
	for(int i=1;i<=n;i++){
		scanf("%lld%lld",&x[i],&y[i]);
		if(y[i]>0) sum+=y[i]; 
	}
	if(sum<k){
		printf("-1");
		return 0;
	}
	//cout<<check(24);
	while(l<r){
		mid=(l+r)>>1;
		if(check(mid)) r=mid;
		else l=mid+1;
	}
	cout<<r;
	return 0;
}