1
//滑动窗口队列+二分+DP
2
//此处二分当模版记住得了
3
//此处j只有在等到满足left后才++，此处把一个区间掰成2步处理很不错，值得借鉴，同时这也是运用队列的原因
4
#include <bits/stdc++.h>
5
using namespace std;
6
typedef long long ll;
7
const ll INF=1e18;
8
ll n,d,k;
9
vector<ll> x,s;
10
bool check(ll t){
11
    vector<ll> gain(n+1,-INF);
12
    deque<ll> dq;
13
    gain[0]=0;
14
    ll j=0;
15
    ll left=max(1LL,d-t),right=d+t;
16
    for(ll i=1;i<=n;i++){
17
        while(j<i&&x[i]-x[j]>=left){
18
            if(gain[j]!=-INF){
19
                while(!dq.empty()&&gain[dq.back()]<gain[j])dq.pop_back();
20
                dq.push_back(j);
21
            }
22
            j++;
23
        }
24
        while(!dq.empty()&&x[i]-x[dq.front()]>right)dq.pop_front();
25
        if(!dq.empty())gain[i]=gain[dq.front()]+s[i];
26
        else gain[i]=-INF;
27
        if(gain[i]>=k)return true;
28
    }
29
    return false;
30
}
31
int main(){
32
    cin>>n>>d>>k;
33
    x.resize(n+1),s.resize(n+1);
34
    for(ll i=1;i<=n;i++)cin>>x[i]>>s[i];
35
    ll r=1e9,l=0;
36
    ll ans=-1;
37
    while(l<=r){
38
        ll mid=(r+l)/2;
39
        if(check(mid)){
40
            ans=mid;
41
            r=mid-1;
42
        }else{
43
            l=mid+1;
44
        }
45
    }
46
    cout<<ans<<endl;
47
    return 0;
48
}