60 pt WA link

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5+10;
int f[N],a[N];
int d,k;
int n;
int x[N];
deque<int> q;
int ct(int mid){
	int l = max(1LL,d-mid),r = d+mid;//
	//l <= xi-xj <= r
	int j = 0;
	q.clear();
	memset(f,-0x3f,sizeof(f));
	int ans = 0;
	f[0] = 0;
	for(int i = 1;i <= n;i++){
		while(!q.empty()&&!(l <= x[i]-x[q.front()]&&x[i]-x[q.front()] <= r)){
		//	cout<<"out "<<q.front()<<endl;
			q.pop_front();
		}
		while(j <= n&&l <= x[i]-x[j]&&x[i]-x[j] <= r){
		//	cout<<j<<" "<<i<<endl;
			while(!q.empty()&&f[q.back()] < f[j])q.pop_back();
			q.push_back(j);
			j++;
		}
		if(!q.empty())f[i] = f[q.front()]+a[i];
	//	cout<<i<<" ans "<<f[i]<<endl;
		ans = max(ans,f[i]);
	}
	return ans;
} 
int find(int l,int r){
	while(l <= r){
		int mid = (l+r)/2;
		//cout<<mid<<" "<<ct(mid)<<" "<<(ct(mid) >= k)<<endl;
		if(ct(mid) >= k)r = mid-1;
		else l = mid+1;
	}
	return l;
}
signed main(){
	cin>>n>>d>>k;
	for(int i = 1;i <= n;i++){
		cin>>x[i]>>a[i];
	}
	if(find(0,x[n]+1) > x[n]){
		cout<<-1;
		return 0;
	}
	cout<<find(0,x[n]+1); 
	return 0;
}