题目描述
$\tt{Mr. M}$ 从 城市$\tt{Z}$($x=0$)出发,初始能量为 $D$,需要骑行 $X$ 米到达 城市$\tt{C}$($x=X$)。每骑行 1 米消耗 1 单位能量,**途中能量不能为负**。
沿途有 $n$ 个餐馆,第 $i$ 个位于 $x_i$ 米处(可能有多个餐馆位于同一位置)。若在 $i$ 号餐馆用餐,能量增加 $y_i$(每个餐馆仅能使用一次)。求到达目的地所需的最少用餐次数,若无法到达输出 $\tt{-1}$。
输入格式
第一行包含三个整数 $n$, $D$, $X$($1 \leq n \leq 2 \times 10^5$,$1 \leq D, X \leq 10^9$)
第二行包含 $n$ 个整数 $x_i$($1 \leq x_i < X$),表示餐馆位置
第三行包含 $n$ 个整数 $y_i$($1 \leq y_i \leq 10^9$),表示能量增益
输出格式
输出最小用餐次数,无法到达输出 $\tt{-1}$
样例输入 #1
5 5 12
3 4 7 8 11
3 2 1 2 1
样例输入 #2
5 10 40
1 20 30 2 38
7 7 7 7 7
样例输入 #3
4 5 12
3 6 9 10
2 1 2 2
提示
第一个样例解释:
- 在 $x=3$ 处剩余能量 $2$ → 用餐后能量 $5$
- 在 $x=4$ 处剩余 $4$ → 用餐后 $6$
- 在 $x=8$ 处剩余 $2$ → 用餐后 $4$
- 总共使用 $3$ 个餐馆