20. Ms. Weasel eats chicken

单点时限: 2.0 sec

内存限制: 256 MB

黄鼠狼姐姐将要踏上一段旅程。她事先规划好了她的旅行线路,因此她知道她将从小镇 $0$ 出发,途径小镇 $1, 2 \ldots n-1$,最终到达小镇 $n$。

出发时,黄鼠狼姐姐的体力值为 $S$。在从小镇 $i-1$ 前往小镇 $i$ 的路途当中,她会消耗体力 $w_i$。

到达小镇 $i$ 后,她可以在这个小镇的饭馆吃一些鸡来恢复体力。由于近几年经济不景气,外加东方神秘力量(据说是鸡年)的影响,每个小镇都只能供应 $1$ 只鸡,并使黄鼠狼姐姐恢复 $x$ 点体力。每个小镇鸡的价格是不同的:小镇 $i$ 中每只鸡的价格为 $P_i$。

黄鼠狼姐姐希望花费尽可能少的钱走完整个旅程。如果黄鼠狼姐姐在某一时刻体力值小于 $0$,她会饿死在半路上。

输入格式

不超过 $50$ 组测试数据。对于每组数据:

第一行三个整数:$n$ $(1 \leq n \leq 10^5)$, $S$ $(0 \leq S \leq 10^9)$, $x$ $(1 \leq x \leq 10^4)$。

第二行 $n$ 个整数,表示 $w_i$ $(0 \leq w_i \leq 10^4)$。

第三行 $n$ 个整数,表示 $P_i$ $(0 \leq P_i \leq 10^4)$。

输出格式

输出黄鼠狼姐姐最少要花多少钱。如果她一定会饿死在半路上,输出 $-1$。

样例

Input
5 3 1
2 1 3 4 5
1 1 1 1 1
5 3 1
1 1 1 1 1
1 2 3 4 5
Output
-1
3

43 人解决,52 人已尝试。

73 份提交通过,共有 228 份提交。

4.0 EMB 奖励。

创建: 7 年,6 月前.

修改: 6 年,9 月前.

最后提交: 1 月,1 周前.

来源: 2017 CCCC 选拔

题目标签