加油站与餐馆(Benzinska)

题目描述

译自 COCI 2024/2025 #4 T2。$\texttt{1s,0.5G}$。满分为 $70$。

在数轴上，Malnar 从原点（$x=0$）出发，前往 $x=X$ 处。

Malnar 初始有 $D$ 单位能量，每走一个单位长度消耗一单位能量。在整个过程中，能量必须不小于 $0$。

有 $n$ 个餐馆，第 $i$ 个餐馆位于 $x=x_i$ 处，在第 $i$ 个餐馆用餐可以使能量增加 $y_i$。至多只能在每个餐馆用一次餐，且不同餐馆的 $x_i$ 可能相同。

求出为了达成目标，至少需要在多少个餐馆用餐。

输入格式

第一行，三个正整数 $n,D,X$。

第二行，$n$ 个正整数 $x_1,\ldots,x_n$。

第三行，$n$ 个正整数 $y_1,\ldots,y_n$。

输出格式

如果不可能，输出一行一个 $\texttt{-1}$。

否则输出一行一个非负整数表示答案。

样例输入 #1

5 5 12
3 4 7 8 11
3 2 1 2 1

样例输出 #1

3

样例输入 #2

5 10 40
1 20 30 2 38
7 7 7 7 7

样例输出 #2

5

样例输入 #3

4 5 12
3 6 9 10
2 1 2 2

样例输出 #3

-1

数据范围

样例解释

样例 $1$ 解释：在第 $1,2,4$ 个餐馆用餐。

数据范围

对于 $100\%$ 的数据，保证：

• $1\le n\le 2\times 10^5$；
• $1\le D,X,y_i\le 10^9$；
• $1\le x_i\lt X$。

• 特殊性质 A：$y_i$ 全相等。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1400。

测试点分布

出处：原题链接