20. Ms. Weasel eats chicken

单点时限: 2.0 sec

内存限制: 256 MB

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

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

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

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

输入格式

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

第一行三个整数: , ,

第二行 个整数,表示

第三行 个整数,表示

输出格式

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

样例

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

30 人解决,34 人已尝试。

53 份提交通过,共有 155 份提交。

4.0 EMB 奖励。

创建: 2 年,9 月前.

修改: 2 年前.

最后提交: 1 月前.

来源: 2017 CCCC 选拔

题目标签