← 返回题目列表

AtCoder · past202303_n

N. 倒垃圾

中文机器翻译题面 查看原题

问题陈述

考虑以下问题。

高桥有 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