AT_discovery_2016_final_b DDPC特別ビュッフェⅡ

DISCO 举办的 Discovery Channel 编程竞赛 2016 决赛的 DDPC 特别自助餐时间开始了。你现在正准备去给你的空托盘装上美食。DDPC 特别自助餐有 $N$ 种不同的菜肴。第 $i$ 种菜肴会在自助餐开始后 $T_i$ 秒消失，该菜肴的美味度为 $A_i$。 DDPC 特别自助餐有以下特殊规则： - 你每次将一种菜肴放到托盘上需要花费 $1$ 秒。也就是说，如果你在时刻 $s$ 开始装菜，那么装完的时刻就是 $s+1$。 - 你不能将同一种菜肴重复放到托盘上。 - 如果当前时刻 $s$ 满足 $s+1 > T_i$，则不能将第 $i$ 种菜肴放到托盘上。 当你托盘上菜肴的美味度总和达到 $X$ 及以上时，你就会回到座位。请你求出使托盘上美味度总和达到 $X$ 及以上所需的最小时刻 $t$。如果无法实现，请输出 $-1$。

输入通过标准输入给出，格式如下： > $N$ $X$ > $T_1$ $T_2$ … $T_N$ > $A_1$ $A_2$ … $A_N$ - 第 $1$ 行包含两个用空格分隔的整数，分别表示 DDPC 特别自助餐中菜肴的种类数 $N(1 \leq N \leq 10^{5})$ 和托盘上美味度总和的目标值 $X(1 \leq X \leq 10^{9})$。 - 第 $2$ 行包含 $N$ 个用空格分隔的整数，第 $i$ 个整数 $T_i (1 \leq T_i \leq 10^{5})$ 表示第 $i$ 种菜肴消失的时刻。 - 第 $3$ 行包含 $N$ 个用空格分隔的整数，第 $i$ 个整数 $A_i (1 \leq A_i \leq 10^{5})$ 表示第 $i$ 种菜肴的美味度。

输出一个整数，表示使托盘上美味度总和达到 $X$ 及以上所需的最小时刻 $t$。如果无法实现，则输出 $-1$。输出末尾请换行。

## 部分分 本题设有部分分。 - 若数据满足 $T_i < T_j$ 时 $A_i \geq A_j$，则该数据集正确可得 $10$ 分。 - 若能通过无额外限制的数据集，则可再得 $40$ 分，合计 $50$ 分。 ## 样例解释 1 - 按如下方式取菜，可以在时刻 $2$ 使托盘上美味度总和达到 $5$ 及以上： - $0$ 秒时，托盘美味度为 $0$，取第 $1$ 种菜。 - $1$ 秒时，托盘美味度为 $3$，取第 $2$ 种菜。 - $2$ 秒时，托盘美味度为 $6$。 - 本例满足部分分的额外限制。 ## 样例解释 2 - 按如下方式取菜，可以在时刻 $3$ 使托盘上美味度总和达到 $10$ 及以上： - $0$ 秒时，托盘美味度为 $0$，取第 $1$ 种菜。 - $1$ 秒时，托盘美味度为 $3$，取第 $2$ 种菜。 - $2$ 秒时，托盘美味度为 $6$，取第 $3$ 种菜。 - $3$ 秒时，托盘美味度为 $10$。 - 本例不满足部分分的额外限制。 ## 样例解释 3 - 按如下方式取菜，可以在时刻 $1$ 使托盘上美味度总和达到 $5$ 及以上： - $0$ 秒时，托盘美味度为 $0$，取第 $3$ 种菜。 - $1$ 秒时，托盘美味度为 $6$。 - 本例满足部分分的额外限制。 ## 样例解释 4 - 无论如何取菜，都无法使托盘上美味度总和达到 $101$ 及以上。 - 本例满足部分分的额外限制。 ## 样例解释 5 - 时刻 $0$ 时无论取哪种菜，另一种菜都会在时刻 $1$ 消失，因此无法使托盘美味度达到 $2$ 及以上。 - 本例满足部分分的额外限制。 ## 样例解释 6 - 按如下方式取菜，可以在时刻 $2$ 使托盘上美味度总和达到 $6$ 及以上： - $0$ 秒时，托盘美味度为 $0$，取第 $2$ 种菜。 - $1$ 秒时，托盘美味度为 $4$，取第 $4$ 种菜。 - $2$ 秒时，托盘美味度为 $6$。 - 本例满足部分分的额外限制。 ## 样例解释 7 - 按如下方式取菜，可以在时刻 $2$ 使托盘上美味度总和达到 $4$ 及以上： - $0$ 秒时，托盘美味度为 $0$，取第 $2$ 种菜。 - $1$ 秒时，托盘美味度为 $2$，取第 $3$ 种菜。 - $2$ 秒时，托盘美味度为 $4$。 - 本例不满足部分分的额外限制。 由 ChatGPT 4.1 翻译