玄关，40 pts 求调

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
using pii=pair<int,int>;
#define fi first
#define se second
constexpr int N=5e5+5;
int n,d,k,q[N],ql,qr;
pii a[N];
ll dp[N];
bool check(int g) {
	int l=max(1,d-g),r=d+g;
	dp[0]=0,ql=1,qr=0;
	for(int i=1,j=0;i<=n;i++) {
		dp[i]=-1e18;
		while(ql<=qr&&a[i].fi-a[q[ql]].fi>r) ql++;
		while(j<i&&a[i].fi-a[j].fi>=l) {
			while(ql<=qr&&dp[q[qr]]<=dp[j]) qr--;
			q[++qr]=j;
			j++;
		}
		if(ql<=qr) dp[i]=dp[q[ql]]+a[i].se;
		if(dp[i]>=k) return 1;
	}
	return 0;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>d>>k;
	for(int i=1;i<=n;i++) cin>>a[i].fi>>a[i].se;
	a[0]={0,0};
	int l=0,r=a[n].fi,ans=-1;
	while(l<=r) {
		int mid=(l+r)>>1;
		if(check(mid)) ans=mid,r=mid-1;
		else l=mid+1;
	}
	cout<<ans<<"\n";
	return 0;
}