AT_past202303_n.ゴミ出し

请考虑如下问题。

Takahashi 在某一天的早晨（记为第 $1$ 天）有 $X$ 千克的垃圾。每晚，垃圾的数量会增加 $1$ 千克。

他有 $N$ 天可以倒垃圾。对于 $i=1,2,\dots,N$，如果他在第 $d_i$ 天早上拥有不少于 $a_i$ 千克的垃圾，他就可以以 $1$ 日元的代价倒掉 $a_i$ 千克垃圾，该操作每一天最多进行一次，也可以不操作。

Takahashi 希望在第 $D$ 天早上垃圾不超过 $C$ 千克。请你求出满足这一条件需要支付的最小金额。

你将得到 $N, C, D, d_i, a_i$。其中 $X$ 是一个非负整数变量。

请找出所有使得 Takahashi 在第 $D$ 天早上垃圾不超过 $C$ 千克的 $X$ 中，所需的最小费用。如果不存在这样的 $X$，则输出 $-1$。

输入从标准输入读入，格式如下：

$ N\ C\ D\ d_1\ a_1\ d_2\ a_2\ \cdots\ d_N\ a_N $

输出答案。

样例解释 1

例如，$X = 2$ 时的一组最优动作如下：

• 第 $1$ 天早上有 $X=2$ 千克垃圾。$d_1=1$，但垃圾不足 $a_1=3$ 千克，因此当天不能倒垃圾。
• 第 $1$ 天晚上后垃圾变为 $3$ 千克。
• 第 $2$ 天晚上后垃圾变为 $4$ 千克。
• 第 $3$ 天早上，用 $1$ 日元倒掉 $a_2=4$ 千克垃圾，这是允许的（$d_2=3$，且$垃圾\geq4$），之后剩余 $0$ 千克垃圾。
• 第 $3$ 天晚上后垃圾变为 $1$ 千克。
• 第 $4$ 天早上有 $1$ 千克垃圾，满足不超过 $C$ 千克的目标。总共花费 $1$ 日元。

样例解释 2

不存在任何 $X$ 使得第 $D$ 天早上垃圾不超过 $C$ 千克。

数据范围

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq C \leq 10^9$
• $1 \leq d_1 < d_2 < \dots < d_N < D \leq 10^9$
• $1 \leq a_i \leq 10^9$
• 所有输入值均为整数。

由 ChatGPT 5 翻译