WA #3,4,5,6,9,10

#include<bits/stdc++.h>
using namespace std;
int n,d,k;
struct Block{
	int dis;
	int sco;
} a[500010];
int dp[500010];
int que[500010],head = 0,tail = 0;
bool check(int c){
	//printf("attempt g = %d::",c);
	memset(que,0,sizeof(que));
	memset(dp,0x80,sizeof(dp));
	head = tail = 0;
	int dismin = max(d-c,1),dismax = d+c;
	int qst = 0; 
	int resul = -2147483648;
	dp[0] = 0;
	//printf("It makes the longest is %d and the shortest is %d\n",dismax,dismin);
	for(int i = 1; i <= n; i++){
		//printf("Jump to block %d[dis=%d  sco=%d]\n",i,a[i].dis,a[i].sco);
		while(a[qst].dis<=a[i].dis-dismin){
			if(dp[qst]==0x80808080){
				qst++;
				continue;
			}
			//printf("The block %d[dis:%d-sco:%d] is need to input\n",qst,a[qst].dis,a[qst].sco);
			while(tail>head&&a[que[tail]].sco<a[qst].sco) tail--;
			que[tail] = qst;
			tail++,qst++;
		}
		while(head<tail&&a[que[head]].dis+dismax<a[i].dis) head++;
		//printf("Repeat the que;head = %d,tail = %d\n",head,tail);
		//for(int rei = head; rei < tail; rei++){
		//	printf("%d[dis:%d,sco:%d]|",que[rei],a[que[rei]].dis,a[que[rei]].sco);
		//}
		//puts("\n");
		if(head>=tail) continue;
		else {
			dp[i] = dp[que[head]]+a[i].sco;
			//printf("%d\n------------\n",dp[i]);
			resul = max(resul,dp[i]);
		}
	}
	//printf("The result is %d\n",resul);
	return resul>=k;
}
int main(){
	//freopen("result.cpp","w",stdout);
	scanf("%d%d%d",&n,&d,&k);
	for(int i = 1; i <= n; i++) scanf("%d%d",&a[i].dis,&a[i].sco);
	int left = 0,right = a[n].dis-d;
	a[0].dis = 0,a[0].sco = 0;
	while(left<=right){
		//printf("%d yu %d\n",left,right);
		int g = (left+right)/2;
		if(check(g)){
			right = g;
			if(left==right) break;
		}
		else left = g+1;
	} 
	if(left>right) printf("-1");
	else printf("%d",right);
	return 0;
}