本来还80分的，加单调队列后，wa345678910

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct st{
	int x,s;
}a[500005];
int b[500005];
int p[500005];
int n,d,k;
int u=1,c=1,c1=1;
bool abc(int g){
	int j=1;
	while (!(a[j].x-d<=g&&a[j].x-d>=-1*g)){
		j++;
	} 
	b[1]=a[j].s;
	j++;
	for (;j<=n;j++){
		int x1=a[j].x-d-g,x2=a[j].x-d+g;
		if (a[j].x-d-g<0) x1=0;
		if (a[j].x-d+g>a[j].x-1) x2=a[j].x-1;
        while (x1>a[u].x&&u<c) u++;
        while (x2>=a[c1].x){
            p[c]=b[c1];
            c1++;
            while (p[c]>p[c-1]&&c>u){
                swap(p[c],p[c-1]);
                c--;
            }
            c++;
        } 
        if (u!=c){
        	b[j]=p[u]+a[j].s;
		}
		if (b[j]>=k){
			return true;
		}
	}
	return false;
}
signed main(){
	cin>>n>>d>>k;
	int o=0;
	for (int i=1;i<=n;i++){
		cin>>a[i].x>>a[i].s;
		if (a[i-1].x==a[i].x){
			if (a[i-1].s<a[i].s){
				swap(a[i-1],a[i]);
			}
			i--;
			n--;
		}
	}
	for (int i=1;i<=n;i++){
		if (a[i].s>0) o+=a[i].s;
	}
	if (o<k){
		cout<<-1;
		return 0;
	}
	a[0].x=0;
	a[0].s=0;
	int l=1,r=a[n].x;
	while (l<r){
		u=c=c1=1;
		int mid=(l+r)/2;
		for (int i=1;i<=500000;i++){
			b[i]=-9223372036854000;
		}
		if (abc(mid)){
			r=mid;
		}else{
			l=mid+1;
		}
	} 
	if (l==a[n].x){
		cout<<-1;
	}else{
		cout<<l;
	}
	return 0; 
}