您正在开发一款新的射击游戏,但由于市面上有很多射击游戏,您决定在游戏中加入一些独特的东西。
你有一把一体化枪,可以按固定顺序发射子弹。弹匣中有 $$$n$$$ 颗子弹,其中第 $$$i$$$ 造成 $$$a_i$$$ 伤害。敌人一开始的生命值是$$$h$$$,当生命值变为$$$\le 0$$$时就会死亡。
枪每秒发射一颗子弹。发射所有 $$$n$$$ 子弹后,必须重新装弹,这需要 $$$k$$$ 秒。重新加载总是会恢复 相同的序列 子弹 $$$[a_1, a_2, \ldots, a_n]$$$。您无法提前重新加载;您必须先清空杂志。一开始,杂志已经满了。
战斗开始前,你可以表演 最多 1 个 交换:选择任何索引 $$$1 \le i \lt 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$$$。
输出
对于每个测试用例,输出一个整数,表示杀死敌人所需的最短时间。
示例
输入复制
65 10 14 2 3 5 35 10 14 2 3 7 33 10 21 2 32 5 32 13 18 51 2 34 10 101 1 2 2
输出复制
32761917
注意
在第一个测试用例中,您交换索引 $$$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$$$ 是不可能的。