2017 T4 跳房子

主知识点：二分。交叉标签：二分、动态规划、单调队列。
暴力标注：DP 可用暴力拿部分分。
OJ 使用标准输入与标准输出。原比赛文件名为 jump.in / jump.out；下方如保留原文件约定，以本句的 OJ 约定为准。
时限 2 秒；内存 256 MiB；测试点 10；总分 100。
数据来源：公开存档数据；未逐文件对照官网下载包。

题目描述

起点坐标为 0，右侧有 $n$ 个坐标严格递增的格子，第 $i$ 个坐标为 $x_i$、分数为 $s_i$。每次只能向右跳至某个格子，经过格子的分数相加，可以随时结束。

机器人原本每次只能跳 $d$。花费非负整数 $g$ 后，每次跳跃长度可以是 $[\max(1,d-g),d+g]$ 中任意整数。求使总得分至少为 $k$ 的最小 $g$；任意改造均无法达成时输出 -1。

输入格式

第一行三个正整数 $n,d,k$，分别表示格子的数目，改进前机器人弹跳的固定距离，以及希望至少获得的分数。相邻两个数之间用一个空格隔开。

接下来 $n$ 行，每行两个整数 $x_i,s_i$，分别表示起点到第 $i$ 个格子的距离以及第 $i$ 个格子的分数。两个数之间用一个空格隔开。保证 $x_i$ 按递增顺序输入。

输出格式

共一行，一个整数，表示至少要花多少金币来改造他的机器人。若无论如何他都无法获得至少 $k$ 分，输出 $-1$。

样例

样例 1

输入：

7 4 10
2 6
5 -3
10 3
11 -3
13 1
17 6
20 2

输出：

2

样例 2

输入：

7 4 20
2 6
5 -3
10 3
11 -3
13 1
17 6
20 2

输出：

-1

数据范围与特殊性质

本题共 10 组测试数据，每组数据等分。

对于全部的数据满足 $1 \le n \le 5\times10^5$，$1 \le d \le2\times10^3$，$1 \le x_i, k \le 10^9$，$|s_i| < 10^5$。

对于第 $1, 2$ 组测试数据，保证 $n\le 10$。

对于第 $3, 4, 5$ 组测试数据，保证 $n \le 500$。

对于第 $6, 7, 8$ 组测试数据，保证 $d = 1$。

附加样例

本题的公开样例整理在对应的“样例”ZIP 中。样例不计入评测测试点；题面中的样例也已保留。

暴力退路标注（教学补充）

DP 可用暴力拿部分分。二分 g 后 DFS 枚举所有向右路径：n≤10 的 1~2 点为 20 分；改为 O(n²) 朴素 DP 检查可覆盖 n≤500 的 1~5 点，目标 50 分。后者仍是 DP，但不要求单调队列优化。

目标范围：20 分 DFS；50 分朴素 DP（按原题规模）。部分分按原题规模判断，不构成对任意实现或评测机的得分保证。

来源与整理说明

题目原作者/发布者：中国计算机学会 CCF / NOI。题意经过改写，保留公式、输入输出、样例及约束；知识点和暴力标注为本次整理补充。

• 题面及约束校对来源：洛谷 CCF_NOI 题目 P3957
• 赛事：NOIP 普及组复赛（CSP-J 前身） 2017。
• 详细数据来源、版本和哈希见总包 来源与校验/manifest.json。