问题陈述
考虑以下问题。
高桥有 X 某天早上(让我们称之为一天)公斤垃圾 1)。每晚垃圾量都会增加 1 公斤。
将会有 N 他可以倒垃圾的日子。对于 i = 1, 2, \dots, N,如果他有 a_i 当天早上垃圾数量或以上 d_i,他可以拿出来 a_i 公斤垃圾,成本为 1 日元零次或一次。
高桥最多想要拥有 C 当天早上的垃圾公斤数 D。找出实现这一目标所需的最低金额。
你被给予 N, C, D, d_i, a_i 作为输入。现在,考虑 X 作为非负整数变量。
找到上述问题的最小答案 X 这样高桥最多可以拥有 C 当天早上的垃圾公斤数 D。 如果没有 X 这样他最多可以拥有 C 当天早上的垃圾公斤数 D,打印 -1.
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq C \leq 10^9
- 1 \leq d_1 \lt d_2 \lt \dots \lt d_N \lt D \leq 10^9
- 1 \leq a_i \leq 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N C D d_1 a_1 d_2 a_2 \vdots d_N a_N
输出
打印答案。
示例输入 1
2 1 4 1 3 3 4
示例输出 1
1
例如,以下是最佳操作顺序: X = 2.
- 一天的早上 1,他有 X = 2 公斤垃圾。我们有 d_1 = 1,但垃圾量小于 a_1 = 3 公斤,所以他今天不能倒垃圾。
- 经过一天的夜晚 1,他有 3 公斤垃圾。
- 经过一天的夜晚 2,他有 4 公斤垃圾。
- 一天的早上 3,他拿出 a_2 = 4 公斤垃圾,成本为 1 日元,这是允许的,因为 d_2 = 3 并且他有不少于 a_2 = 4 公斤垃圾。那么,他有 0 公斤垃圾。
- 经过一天的夜晚 3,他有 1 公斤垃圾。
- 一天的早上 4,他有 1 公斤垃圾,不超过 C 千克,因此满足目标。他付了钱 总计 1 日元。
示例输入 2
3 10 100 10 20 20 20 30 20
示例输出 2
-1
没有 X 这样他最多可以拥有 C 当天早上的垃圾公斤数 D.
示例输入 3
4 4 10 2 3 4 5 6 1 8 4
示例输出 3
2