T了，只有80分

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(!isdigit(c)){f=-1;c=getchar();};
	while(isdigit(c)){x=x*10+c-'0';c=getchar();};
	return x*f;
}
ll ans=1e9,n,d,k,maxx,mid;
ll dist[500005],num[500005],cnt[500005];
bool check(int x){
	int lw=d-x,rw=d+x;
	lw=max(1,lw);
	for(int i=0;i<=n;i++){
		cnt[i]=-1e9;
	}
	cnt[0]=0;
	for(int i=0;i<n;i++){
		for(int j=i+1;j<=n;j++){
			if(dist[j]-dist[i]>=lw && dist[j]-dist[i]<=rw){
				cnt[j]=max(cnt[j],cnt[i]+num[j]);
				if(cnt[j]>=k) return 1;
			}
			else{
				if(dist[j]-dist[i]>lw) break;
			}
		}
	}
	return 0;
}
int main(){
	n=read(),d=read(),k=read();
	for(int i=1;i<=n;i++){
		dist[i]=read(),num[i]=read();
		maxx=max(maxx,dist[i]);
	}
	dist[0]=0,num[0]=0;
	ll l=0,r=maxx-d;
	while(l<=r){
		mid=l+(r-l)/2;
//		cout<<mid<<endl;
		if(check(mid)){
			ans=min(ans,mid);
			r=mid-1;
		}
		else l=mid+1;
//		for(int i=1;i<=n;i++) cout<<cnt[i]<<" ";
//		cout<<endl;
	}
	if(ans==1e9) cout<<"-1";
	else cout<<ans;
	return 0;
}