作者：李济民233
链接：https://www.nowcoder.com/discuss/123368?type=0&order=0&pos=6&page=0
来源：牛客网
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=500010;
const ll INF=(ll)(1e9)*maxn;
int n,d,dis[maxn];
ll k,val[maxn];
ll dp[maxn];
deque<int> q;
int zuo,you;
bool in_range(int j,int i)
{
    return zuo<=dis[i]-dis[j]&&dis[i]-dis[j]<=you;
}
bool test(int g)
{
    if(g>=d)
    {
        zuo=1;
        you=d+g;
    }
    else
    {
        zuo=d-g;
        you=d+g;
    }
    for(int i=1;i<=n;i++)
    dp[i]=-INF;
    int L=0;
    q=deque<int>();
    for(int i=1;i<=n;i++)
    {
        if(zuo<=dis[i]&&dis[i]<=you)
        dp[i]=val[i];
        while(1)
        {
            if(L+1>=i)
            break;
            if(dis[i]-dis[L+1]<zuo)
            break;
            L++;
            if(dp[L]==-INF)
            continue;
            while(!q.empty()&&dp[q.back()]<=dp[L])
            q.pop_back();
            q.push_back(L);
        }
        while(!q.empty()&&!in_range(q.front(),i))
        q.pop_front();
        if(!q.empty())
        dp[i]=max(dp[i],dp[q.front()]+val[i]);
        if(dp[i]>=k)
        return 1;
    }
    return 0;
}
int main()
{
    scanf("%d %d %lld",&n,&d,&k);
    int mx=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d %lld",&dis[i],&val[i]);
        mx=max(mx,dis[i]);
    }
    int l=0,r=mx,ans=-1;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(test(mid))
        {
            r=mid-1;
            ans=mid;
        }
        else l=mid+1;
    }
    printf("%d\n",ans);
    return 0;
}