CF2192C.All-in-one Gun

You are developing a new shooter game, but since there are a lot of shooter games out there, you decide to have something unique in your game.

You have an all-in-one gun that shoots bullets in a fixed order. There are $n$ bullets in the magazine, the $i$-th of which deals $a_i$ damage. The enemy starts with $h$ health and dies when its health becomes $\le 0$.

The gun shoots one bullet per second. After firing all $n$ bullets, it must reload, which takes $k$ seconds. Reloading always restores the same sequence of bullets $[a_1, a_2, \ldots, a_n]$. You cannot reload early; you must empty the magazine first. At the start, the magazine is already full.

Before the fight begins, you may perform at most one swap: pick any indices $1 \le i \lt j \le n$ and exchange $a_i$ with $a_j$.

Your task is to find the minimum number of seconds needed to kill the enemy, taking into account this optional single swap.

你正在开发一款全新的射击游戏，但由于市面上已存在大量同类游戏，你决定为自己的游戏加入一些独特元素。

你拥有一把“全能型”枪械，它以固定顺序发射子弹。弹匣中共有 $n$ 发子弹，其中第 $i$ 发子弹造成 $a_i$ 点伤害。敌人初始生命值为 $h$，当其生命值 $\le 0$ 时即被击杀。

该枪每秒发射一发子弹。射完全部 $n$ 发子弹后，必须进行装填，耗时 $k$ 秒。每次装填均会恢复完全相同的子弹序列 $[a_1, a_2, \ldots, a_n]$。你不能提前装填；必须先将弹匣打空。游戏开始时，弹匣已处于满载状态。

在战斗开始前，你最多可执行一次交换操作：任选下标 $1 \le i \lt j \le n$，交换 $a_i$ 与 $a_j$ 的值。

你的任务是：考虑这一可选的单次交换操作，求出击杀敌人所需的最短时间（单位：秒）。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each testcase contains three integer $n$, $h$ and $k$ ($2 \le n \le 2\cdot 10^5$, $ 1 \le h, k \le 10^9$) — the size of magazine, health of your enemy and time required to reload the magazine.

The second line of each testcase contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$).

It is guaranteed that the sum of $n$ does not exceed $2 \cdot 10^5$ over all test cases.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each testcase, output a single integer denoting the minimum time required to kill the enemy.

对于每个测试用例，输出一个整数，表示击杀敌人的最短时间。

In the first test case, you swap the bullets present at index $2$ and $5$. This makes array $a$ as $4, 3, 3, 5, 2$.

After $3$ seconds, the health of your enemy will be $10 - 4 - 3 - 3 = 0$, hence the enemy dies in $3$ seconds. It can be shown that achieving time to kill less than $3$ is not possible.

In the third test case, you swap bullets present at index $1$ and $3$. This makes array $a$ as $3, 2, 1$.

In $7$ seconds, you shoot the entire first magazine ($3$ seconds) $+$ reload a new magazine ($2$ seconds) $+$ shoot the first and the second bullet from the new magazine ($2$ seconds).

The health of the enemy will be $10 - 3 - 2 - 1 - 3 - 2 = -1$, hence the enemy dies in $7$ seconds. It can be shown that achieving time to kill less than $7$ is not possible.

在第一个测试用例中，你交换了索引为 $2$ 和 $5$ 处的子弹。这使得数组 $a$ 变为 $4, 3, 3, 5, 2$。

经过 $3$ 秒后，敌人的生命值为 $10 - 4 - 3 - 3 = 0$，因此敌人在 $3$ 秒内死亡。可以证明，无法将击杀时间缩短至少于 $3$ 秒。

在第三个测试用例中，你交换了索引为 $1$ 和 $3$ 处的子弹。这使得数组 $a$ 变为 $3, 2, 1$。

在 $7$ 秒内，你完成了以下操作：射空第一本弹匣（耗时 $3$ 秒）$+$ 更换新弹匣（耗时 $2$ 秒）$+$ 从新弹匣中射出第一颗和第二颗子弹（耗时 $2$ 秒）。

敌人的生命值为 $10 - 3 - 2 - 1 - 3 - 2 = -1$，因此敌人在 $7$ 秒内死亡。可以证明，无法将击杀时间缩短至少于 $7$ 秒。