WA on #2 4 9 10.

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
typedef unsigned long long ull;
int n,d,k;
int l,r,mid,ans=-1;
pii a[500005];
ll dp[500005];
priority_queue<pii>q;
bool check(int x){
	memset(dp,0,sizeof(dp));
	while(!q.empty())q.pop();
	int pl=1,pr=1,tl=max(1,d-x),tr=d+x;
	dp[1]=a[1].second;
	q.push({dp[1],1});
	for(int i=2;i<=n;i++){
		while(a[pr+1].first+tl<=a[i].first){
			pr++;
			q.push({dp[pr],pr});
		}
		while(a[pl].first+tr<a[i].first)pl++;
		while(!q.empty()&&q.top().second<pl)q.pop();
		if(q.empty())return 0;
		dp[i]=q.top().first+a[i].second;
		if(dp[i]>=k)return 1;
	}
	return 0;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>d>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i].first>>a[i].second;
		r=max(r,a[i].first);
	}
	l=0;
	while(l<=r){
		mid=(l+r)>>1;
		if(check(mid)){
			ans=mid;
			r=mid-1;
		}
		else l=mid+1;
	}
	if(ans!=-1)cout<<ans;
	else cout<<-1;
	return 0;
}