← 返回题目列表

Codeforces · 1218/F

F. 锻炼计划

中文机器翻译题面 查看原题

艾伦决定在夏天保持体形,因此他制定了一个精确的锻炼计划来遵循。他的计划是在接下来的 N 天里每天去不同的健身房,并在 $$$i$$$ 日举起 $$$X[i]$$$ 克。为了提高他在健身房的锻炼表现,他可以在他目前所在的健身房购买一杯锻炼前饮料,这将立即永久提高他的表现 $$$A$$$ 克。在不同的健身房中,由于口味和健身房的位置,这些锻炼前饮料的价格可能会有所不同 $$$C[i]$$$,但其永久的锻炼收益是相同的。在开始锻炼计划的第一天之前,艾伦知道他最多可以举起 $$$K$$$ 克。帮助艾伦花费最低总金额以实现他的锻炼计划。如果他无法成功完成锻炼计划,则输出$$$-1$$$。

输入

第一个包含两个整数,整数 $$$N$$$ $$$(1 \leq N \leq 10^5)$$$ 和 $$$K$$$ $$$(1 \leq K \leq 10^5)$$$ – 分别代表锻炼计划中的天数以及他在开始锻炼计划之前可以举起的克数。第二行包含 $$$N$$$ 整数 $$$X[i]$$$ $$$(1 \leq X[i] \leq 10^9)$$$ 用一个空格分隔,表示艾伦在 $$$i$$$ 那天想要举起多少克。第三行包含一个整数 $$$A$$$ $$$(1 \leq A \leq 10^9)$$$ 代表单次饮料的永久性能提升。最后一行包含 $$$N$$$ 整数 $$$C[i]$$$ $$$(1 \leq C[i] \leq 10^9)$$$ ,表示他在 $$$i$$$ 那天去健身房的运动增强饮料的成本。

输出

一个整数,代表完成他的锻炼计划所花费的最少费用。如果他无法完成锻炼计划,则输出-1。

示例

输入 #1

5 10000
10000 30000 30000 40000 20000
20000
5 2 8 3 6

输出 #1

5

输入 #2

5 10000
10000 40000 30000 30000 20000
10000
5 2 8 3 6

输出 #2

-1

注意

第一个示例:在第 2 天和第 4 天购买饮料后,Alan 可以完成他的锻炼计划。第二个例子:艾伦在第二天无法举起 40000 克。