我运行了如下代码（a.cpp 为二分 check 函数复杂度 $n^2$ 的代码，在本题能够通过）

#include <bits/stdc++.h>
#define int long long
signed main()
{
    freopen("hack.out", "w", stdout);
    printf("500000 1 500000\n");
    for (int i = 1; i <= 499999; i++)
    {
        printf("%lld 1\n", i);
    }
    printf("1000000000 1\n");
    fclose(stdout);
    freopen("con", "w", stdout);
    system("g++ a.cpp -o a.exe -std=c++14 -O2");
    int ti = clock();
    printf("Running...\n");
    system(".\\a.exe");
    printf("\nRun time:%lldms", (clock() - ti) * 1000 / CLOCKS_PER_SEC);
}

a.cpp 代码为：

#include <bits/stdc++.h>
#define int long long
#define fir first
#define sec second
using namespace std;
int n, d, k, a[500005], b[500005], f[500005];
inline bool check(int x)
{
    memset(f, 0x80, sizeof f);
    f[0] = 0;
    int l = max(d - x, 1ll), r = d + x;
    for (int i = 1; i <= n; i++)
    {
        for (int j = i - 1; j >= 0; j--)
        {
            if (a[i] - a[j] < l)
                continue;
            if (a[i] - a[j] > r)
                break;
            f[i] = max(f[i], b[i] + f[j]);
            if (f[i] >= k)
                return 1;
        }
    }
    return 0;
}
signed main()
{
    freopen("hack.out", "r", stdin);
    scanf("%lld %lld %lld", &n, &d, &k);
    for (int i = 1; i <= n; i++)
        scanf("%lld %lld", &a[i], &b[i]);
    int l = 0, r = 2000;
    while (l < r)
    {
        int mid = (l + r >> 1);
        if (check(mid))
            r = mid;
        else
            l = mid + 1;
    }
    printf("%lld", l);
    return 0;
}

运行时间结果多次测量在 $13900$ 至 $14200$ 之间波动。

求添加该 hack 数据。

方便管理纯构造 hack 数据的代码：

#include <bits/stdc++.h>
#define int long long
signed main()
{
    freopen("hack.out", "w", stdout);
    printf("500000 1 500000\n");
    for (int i = 1; i <= 499999; i++)
    {
        printf("%lld 1\n", i);
    }
    printf("1000000000 1\n");
    fclose(stdout);
}