CF1218F.Workout plan

普及/提高-

通过率:0%

时间限制:1.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Alan decided to get in shape for the summer, so he created a precise workout plan to follow. His plan is to go to a different gym every day during the next N days and lift X[i]X[i] grams on day ii. In order to improve his workout performance at the gym, he can buy exactly one pre-workout drink at the gym he is currently in and it will improve his performance by AA grams permanently and immediately. In different gyms these pre-workout drinks can cost different amounts C[i]C[i] because of the taste and the gym's location but its permanent workout gains are the same. Before the first day of starting his workout plan, Alan knows he can lift a maximum of KK grams. Help Alan spend a minimum total amount of money in order to reach his workout plan. If there is no way for him to complete his workout plan successfully output −1-1.

艾伦决定为夏天塑形,因此制定了一份精确的锻炼计划。根据该计划,他在接下来的 NN 天中每天前往一家不同的健身房,并在第 ii 天举起 X[i]X[i] 克重物。为了提升自己在健身房的训练表现,他可以在当前所在的健身房恰好购买一瓶运动前饮剂,该饮剂会立即且永久地提升他的举重能力 AA 克。由于口味和健身房地理位置不同,各健身房中该运动前饮剂的价格 C[i]C[i] 各不相同,但其带来的永久性增益效果(即 AA 克)始终相同。在开始锻炼计划的第一天之前,艾伦已知自己最多能举起 KK 克重物。请帮助艾伦计算出完成全部锻炼计划所需的最小总花费。若无法成功完成整个锻炼计划,请输出 −1-1。

输入格式

The first one contains two integer numbers, integers NN (1≤N≤105)(1 \leq N \leq 10^5) and KK (1≤K≤105)(1 \leq K \leq 10^5) – representing number of days in the workout plan and how many grams he can lift before starting his workout plan respectively. The second line contains NN integer numbers X[i]X[i] (1≤X[i]≤109)(1 \leq X[i] \leq 10^9) separated by a single space representing how many grams Alan wants to lift on day ii. The third line contains one integer number AA (1≤A≤109)(1 \leq A \leq 10^9) representing permanent performance gains from a single drink. The last line contains NN integer numbers C[i]C[i] (1≤C[i]≤109)(1 \leq C[i] \leq 10^9) , representing cost of performance booster drink in the gym he visits on day ii.

第一行包含两个整数 NN(1≤N≤1051 \leq N \leq 10^5)和 KK(1≤K≤1051 \leq K \leq 10^5),分别表示训练计划的天数以及 Alan 在开始训练计划前能举起的重量(单位:克)。
第二行包含 NN 个整数 X[i]X[i](1≤X[i]≤1091 \leq X[i] \leq 10^9),以单个空格分隔,表示 Alan 在第 ii 天希望举起的重量(单位:克)。
第三行包含一个整数 AA(1≤A≤1091 \leq A \leq 10^9),表示每次饮用性能增强饮料所带来的永久性能力提升(单位:克)。
最后一行包含 NN 个整数 C[i]C[i](1≤C[i]≤1091 \leq C[i] \leq 10^9),表示 Alan 在第 ii 天所访问的健身房中性能增强饮料的价格。

输出格式

One integer number representing minimal money spent to finish his workout plan. If he cannot finish his workout plan, output -1.

一个整数,表示完成训练计划所需的最少花费。如果无法完成训练计划,则输出 -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

说明/提示

First example: After buying drinks on days 2 and 4 Alan can finish his workout plan. Second example: Alan cannot lift 40000 grams on day 2.

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

输入解题思路,AI测评打分。不知道怎么写?

首页