//单调队列优化Dp
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int N = 5e5+10;
typedef long long LL;
const LL INF = 0x3f3f3f3f3f3f3f3f;
LL n, d, k;
LL f[N];
LL x[N] , w[N];
int q[N]; //维护的单调队列
//其实基本上这种双端限制的单调队列的优化思路和模版都是差不多的
//都是先二分可能解,每次判断都使用单调队列
//在单调队列内部实现是,都是用j来表示轮到哪个元素入队,基本上都是如此
bool check(LL g)
{
memset(f , -0x3f , sizeof f);
LL l = max(1LL , d - g) , r = d + g;
int hh = 0 , tt = -1;
f[0] = 0;
//这个是真正的核心,表示的是当前该轮到哪个元素需要进队了,
//这样就直接保证了不需要再用二分查找那个元素需要进队
int j = 0;
for(int i = 1 ; i <=n ; i ++)
{
//然后将能够到达i点的心得点依次进队
while(j < i && x[i] - x[j] >= l)
{
//如果当前这个点是能够到达的有效的点的话,就直接进队
if(f[j] > -1e18)
{
while(tt >= hh && f[q[tt]] <= f[j]) tt --;
q[++ tt] = j;
}
j ++;
}
//将超出能到i点的点集的点出队
while(tt >= hh && x[i] - x[q[hh]] > r) hh ++;
if(tt >= hh) f[i] = f[q[hh]] + w[i]; //只有队列不空的是后才能计算,否则会出问题
}
LL res = -INF;
for(int i = 0 ; i<=n; i ++) res = max(res , f[i]);
return res >= k;
}
int main()
{
scanf("%lld%lld%lld",&n , &d , &k);
for(int i = 1 ; i <=n; i ++) scanf("%lld%lld",&x[i] , &w[i]); //注意读入,读入的是long long
LL l = 0 , r = 1e9+7;
while(l < r)
{
LL mid = l + r >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
if(r > 1e9) cout << -1 << endl;
else cout << l << endl;
return 0;
}
//这个是最基本的方法,在check函数的内部是可以优化的,使用单调队列进行优化维护一个特定长度的区间内f[j]的最大值即可
#include <cstring>
#include <iostream>
#define x first
#define y second
using namespace std;
const int N = 500010;
int n, d, k;
long long f[N], l, r = 1005, mid;
pair<long long, long long> s[N];
bool check(long long g)
{
memset(f, 0xcf, sizeof f);
f[0] = 0;
long long lg = d - g, rg = d + g;
if (lg <= 0) lg = 1;
for (int i = 1; i <= n; i ++ )
{
for (int j = i - 1; j >= 0; j -- )
if (s[i].x - s[j].x >= lg && s[i].x - s[j].x <= rg) f[i] = max(f[i], f[j] + s[i].y);
else if(s[i].x - s[j].x > rg) break;
if (f[i] >= k) return 1;
}
return 0;
}
int main()
{
cin >> n >> d >> k;
for (int i = 1; i <= n; i ++ ) cin >> s[i].x >> s[i].y;
while(l < r)
{
mid = l + r >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
if (l == 1005) puts("-1");
else cout << l;
return 0;
}