版权声明

本题版权归 所有。

题目来源暂未公开。

题目描述

你带着可供行驶 $p$ 千米的汽油驾车在一条笔直的公路上行驶。

公路旁边有 $n$ 个加油站，第 $i$ 个加油站在前方 $a_i$ 千米处，提供可供行驶 $b_i$ 千米的汽油。

请问你至少要停下来多少次进行加油才能抵达在你前方 $q$ 千米处的目的地？

在本题中，我们做出如下约定：

• 你可以在汽油刚好用完时停车、加油或到达目的地。
• 你可以在一次停车内在多个重合的加油站处加油。
• 到达目的地后不必停车。

输入格式

本题有多组数据。

对于每组数据：

第一行三个正整数 $n, p, q\ (1 \le n \le 10^6, 1 \le p < q \le 10^9)$。

第二行 $n$ 个正整数 $a_1, a_2, \ldots, a_n\ (0 < a_i < q)$。

第三行 $n$ 个正整数 $b_1, b_2, \ldots, b_n\ (0 < b_i < q)$。

输入以 EOF 结束。

保证输入的数字个数不超过 $2 \times 10^6$。

输出格式

对于每组数据，输出一行一个整数表示答案。

特别地，如果不可能到达目的地，输出 $\bm{-1}$。

样例

7 23 50
10 15 18 31 35 36 42
4 7 6 12 16 10 9
7 10 50
10 15 18 31 35 36 42
4 7 6 12 16 10 9
6 11 77
11 11 11 11 11 11
11 11 11 11 11 11
6 11 77
11 22 33 44 55 66
11 11 11 11 11 11

3
-1
1
6