← 返回题目
题库练习 All-in-one Gun
← 上一题 下一题 →

A16780 | All-in-one Gun

时间限制1s
内存限制256MB
通过 / 提交0/0

题目描述

你正在开发一款新的射击游戏，但鉴于市面已有大量射击游戏，你决定让游戏具有独特之处。

你拥有一把多合一武器，它会以固定顺序射出子弹。弹夹中有 $n$ 发子弹，第 $i$ 发的伤害为 $a_i$。敌人初始拥有 $h$ 点生命值，当其生命值降至 $0$ 或更低时死亡。

武器每秒射出一发子弹，打完所有 $n$ 发后必须重新装填，装填需要 $k$ 秒。装填后弹夹重新变为同样的顺序 $[a_1, a_2, \ldots, a_n]$。你不能提前装填，必须先打空弹夹。一开始弹夹已经填满。

战斗开始前，你最多只允许进行一次交换操作：任选下标 $1 \le i < j \le n$，将 $a_i$ 与 $a_j$ 进行交换。

你的任务是，考虑可选的这一轮交换后，求击杀敌人所需的最少秒数。

输入格式

每组测试数据包含多个测试用例。第一行包含整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

每组测试数据的第一行包含三个整数 $n$、$h$ 和 $k$（$2 \le n \le 2\cdot 10^5$，$1 \le h, k \le 10^9$）——弹夹容量、敌人生命值以及重新装填所需时间。

每组测试数据的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$）。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每组测试数据，输出一个整数，表示击杀敌人所需的最小时间（单位为秒）。

输入输出样例

输入 #1
6
5 10 1
4 2 3 5 3
5 10 1
4 2 3 7 3
3 10 2
1 2 3
2 5 3
2 1
3 18 5
1 2 3
4 10 10
1 1 2 2
输出 #1
3
2
7
6
19
17
C++ 编辑器
输入
输出