题目描述

在一个魔法世界里，勇士需要穿越一个危险的迷宫。迷宫中有 $n$ 个房间排成一排，从左至右编号为 $1$ 至 $n$，勇士需要按照从左至右的顺序从第 $1$ 个房间开始一直到走出第 $n$ 个房间才可以穿越成功，每个房间都存在魔法护盾和魔法攻击。

魔法护盾可以累积，但有最大容量限制。第 $i$ 个房间有 $s_i$ 个魔法护盾（可能为负，表示护盾被消耗），护盾最大累积容量为 $c$。

同时，每个房间可能有魔法攻击，$a_i$ 表示第 $i$ 个房间的攻击力。如果勇士在房间中累积的护盾小于攻击力，则会导致勇士穿越失败。

关键规则：

• 初始时，勇士拥有 $b$ 个护盾。
• 进入房间 $i$ 时，先获得 $s_i$ 护盾（$s_i < 0$ 表示失去 $|s_i|$ 护盾），然后面临 $a_i$ 攻击。
• 护盾有上限，累积护盾不能超过 $c$，若获得护盾后护盾大于 $c$，则护盾立即变为 $c$。
• 如果在任何房间中，护盾数量小于攻击力，冒险失败。
• 可以选择性地从某些房间中获得“护盾增幅”效果，选择增幅的房间，$s_i$ 的效果会翻倍，该效果不影响 $a_i$。

请计算勇士要成功通过所有房间，最少需要对多少个房间使用护盾增幅？如果无论如何都无法通过迷宫，则输出整数 $-1$。

输入格式

输入的第一行包含三个整数 $n, c, b$，相邻整数之间使用一个空格分隔，分别表示房间数量、护盾最大容量和初始护盾。

第二行包含 $n$ 个整数 $s_1, s_2, \dots, s_n$，相邻整数之间使用一个空格分隔，$s_i$ 表示第 $i$ 个房间的护盾变化。

第三行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，相邻整数之间使用一个空格分隔，$a_i$ 表示第 $i$ 个房间的攻击力。

输出格式

输出一行包含一个整数表示答案，即成功通过迷宫所需的最少护盾增幅房间数量。如果无法通过迷宫，请输出整数 $-1$。

5 9 2
6 -3 6 -1 -4
9 6 6 7 4

1

9 9 0
5 3 9 5 -3 7 -1 3 -5
3 4 3 4 2 8 5 1 3

0

提示

样例说明 1

对第一个房间使用护盾增幅。

到达第 $1$ 个房间，当前护盾值为 $\min(2 + 6 \times 2, 9) = 9 \ge 9$，可以通过第 $1$ 个房间。

到达第 $2$ 个房间，当前护盾值为 $9 - 3 = 6 \ge 6$，可以通过第 $2$ 个房间。

到达第 $3$ 个房间，当前护盾值为 $\min(6 + 6, 9) = 9 \ge 6$，可以通过第 $3$ 个房间。

到达第 $4$ 个房间，当前护盾值为 $9 - 1 = 8 \ge 7$，可以通过第 $4$ 个房间。

到达第 $5$ 个房间，当前护盾值为 $8 - 4 = 4 \ge 4$，可以通过第 $5$ 个房间。所以答案为 $1$。

样例说明 2

不需要使用护盾增幅，就可以通过所有房间。

评测用例规模与约定

对于 $25\%$ 的评测用例，$1 \le n \le 10$；

对于 $50\%$ 的评测用例，$1 \le n \le 20$；

对于 $60\%$ 的评测用例，$1 \le n \le 50$；

对于 $70\%$ 的评测用例，$1 \le n \le 100$；

对于 $80\%$ 的评测用例，$1 \le n \le 1000$；

对于所有评测用例，$1 \le n \le 10000$，$-10000 \le s_i \le 10000$，$1 \le a_i \le 10000$，$1 \le c \le 50000$，$0 \le b \le 50000$。