C. Универсальное оружие
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы разрабатываете новую игру-шутер, но поскольку существует много игр-шутеров, вы решаете сделать что-то уникальное в вашей игре.

У вас есть универсальное оружие, которое стреляет пулями в фиксированном порядке. В магазине $$$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$$$.

Ваша задача — найти минимальное количество секунд, необходимых для убийства врага, учитывая эту опциональную единственную замену.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — минимальное время, необходимое для убийства врага.

Пример
Входные данные
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
Выходные данные
3
2
7
6
19
17
Примечание

В первом наборе входных данных вы меняете местами пули, находящиеся на индексах $$$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$$$ невозможно.