CFCF2192C.All-in-one Gun

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

你拥有一把多合一武器，它会以固定顺序射出子弹。弹夹中有 $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$。

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

在第一个测试用例中，你可以交换下标为 $2$ 和 $5$ 的子弹。交换后数组 $a$ 变为 $4, 3, 3, 5, 2$。

经过 $3$ 秒，敌人的生命值为 $10 - 4 - 3 - 3 = 0$，因此 $3$ 秒内击杀敌人。可以证明无法用更短时间击杀敌人。

在第三个测试用例中，你可以交换下标 $1$ 和 $3$ 的子弹。交换后数组 $a$ 变为 $3, 2, 1$。

第 $7$ 秒时，你射光第一轮弹夹（$3$ 秒）+ 装填新弹夹（$2$ 秒）+ 用新弹夹射出前两发（$2$ 秒），共用时 $7$ 秒。

此时敌人生命值为 $10 - 3 - 2 - 1 - 3 - 2 = -1$，因此 $7$ 秒内击杀敌人。可以证明无法用更短时间完成。

由 ChatGPT 5 翻译