#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,d,k;
int x[500005],s[500005];
int dp[500005];
deque<int> q;
bool check(int g){
	memset(dp,0xcf,sizeof(dp));
	dp[0]=0;
	q.clear();
	int l=max((long long)1,d-g);
	int r=d+g;
	int k=0;
	for(int i=1;i<=n;i++){
		while(x[k]+l<=x[i]) {
			if(dp[k]!=0xcfcfcfcfcfcfcfcf){
				while(!q.empty() && dp[q.back()]<=dp[k]) q.pop_back();
				q.push_back(k);
			}
			k++;
		}
		while(!q.empty() && x[q.front()]+r<x[i]) q.pop_front();
		if(!q.empty()) dp[i]=dp[q.front()]+s[i];
		if(dp[i]>=k) return true;
	}
	return false;
}
signed main(){
	cin>>n>>d>>k;
	for(int i=1;i<=n;i++){
		cin>>x[i]>>s[i];
	}
	int l=0,r=x[n];
	while(l+1<r){
		int mid=(l+r)/2;
		if(check(mid)) r=mid;
		else l=mid;
	}
	cout<<l;
	return 0;
}

全WA