Skip to content

14104: 【原4104】work

题目

题目描述

author: Lmxyy 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4104

Description

xyy这个月决定开始打工。假设月初时xyy有\(E\)点体力。

接下来每一天xyy都会接到一份工作,这份任务xyy可以用任意非负整数体力去完成。并且当天结束之后,xyy会开始养肝,回复\(R\)点体力。当然由于月初时xyy体力是满的,所以如果当前体力增加\(R\)大于\(E\),回复完后体力依旧是\(E\)。毫无疑问,xyy体力也不可能小于\(0\)。

每个工作都会有一个价值\(V_i\),一个工作的报酬就是这个工作的价值乘上对这个工作付出的体力。

由于xyy的精力都去工作了,所以xyy想要问你他最多能够获得多少钱?

Input Format

第一行一个正整数\(case\),表示数据组数。

对于每组数据,第一行三个正整数\(E,R,N\),分别表示体力上限、每天体力的恢复值以及这个月的天数。第二行有\(N\)个非负整数表示\(V_1 \sim V_N\)。

Output Format

对于每组数据,输出一行,表示xyy能够获得的最大工资。

Sample Input

1
5 2 2
2 1

Sample Output

12

Data Range

| 数据编号 | \(case\) | \(N\) | \(E\) | | :------: | :--------: | :----------: | :--------: | | 1 | \(10\) | \(10\) | \(10\) | | 2 | \(100\) | \(100\) | \(100\) | | 3 | \(100\) | \(100\) | \(1000\) | | 4 | \(100\) | \(10\) | \(10^6\) | | 5 | \(100\) | \(10000\) | \(10^6\) | | 6 | \(100\) | \(10000\) | \(10^6\) | | 7 | \(5\) | \(100000\) | \(10^6\) | | 8 | \(5\) | \(500000\) | \(10^6\) | | 9 | \(5\) | \(500000\) | \(10^6\) | | 10 | \(5\) | \(500000\) | \(10^6\) |

数据保证所有输入非负,并且\(V_i \le 10^6\)。

Hint

由于输入数据较多,建议使用读入优化。

如果你写的正解却发现re,建议看看数据范围。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!