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

Таня планирует разобрать свой книжный шкаф. В шкафу есть $$$n$$$ полок для книг, на $$$i$$$-й полке лежит $$$a_i$$$ книг. Таня будет довольна, если на каждой полке будет лежать не более $$$k$$$ книг.

Таня может совершать одну из двух операций, чтобы достичь желаемого:

  1. Выбрать ровно одну книжную полку и убрать все книги с нее в кладовку (то есть выбрать некоторое $$$i$$$ и присвоить $$$a_i := 0$$$). На эту операцию она тратит $$$x$$$ секунд.
  2. Взять все книги со всех $$$n$$$ полок и распределить их по всем $$$n$$$ полкам равномерно (определение этого понятия написано ниже). На эту операцию она тратит $$$y$$$ секунд.

Рассмотрим последовательность $$$a$$$ из $$$n$$$ целых чисел. Тогда ее равномерное распределение — это такая последовательность $$$b$$$ из $$$n$$$ целых чисел, что сумма $$$b$$$ равна сумме $$$a$$$, а значение $$$max(b) - min(b)$$$ минимально возможное.

Например, если массив $$$a=[5, 4, 3]$$$, то его равномерное распределение — это $$$b=[4, 4, 4]$$$. Если $$$a=[1, 2, 3, 4]$$$, то его равномерное распределение — это $$$b=[2, 3, 3, 2]$$$ (или любая другая перестановка этого массива).

Ваша задача — найти минимальное количество секунд, за которое Таня сможет получить книжный шкаф с не более чем $$$k$$$ книгами на каждой полке.

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

В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Затем следуют $$$t$$$ наборов.

В первой строке набора входных данных записаны четыре целых числа $$$n, k, x$$$ и $$$y$$$ ($$$1 \le k \le n \le 2 \cdot 10^5; 1 \le x, y \le 10^4$$$) — количество книжных полок, максимальное разрешенное количество книг на каждой полке и количество секунд, которые Таня тратит на первую и вторую операцию, соответственно.

Во второй строке набора входных данных записаны $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$), где $$$a_i$$$ — это количество книг на $$$i$$$-й полке.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$).

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

Для каждого набора входных данных выведите ответ — минимальное количество секунд, необходимые Тане, чтобы получить книжный шкаф такой, что на каждой полке стоит не более $$$k$$$ книг.

Пример
Входные данные
6
5 4 3 5
1 2 2 3 5
5 3 4 5
1 5 1 5 5
5 4 5 6
1 2 5 3 5
4 3 2 10
4 4 1 1
4 3 10 2
4 4 1 1
4 1 5 4
1 2 1 3
Выходные данные
3
9
6
4
2
9
Примечание

В первом наборе входных данных примера будет оптимальным совершить первую операцию над пятой книжной полкой. Таким образом, массив $$$a$$$ станет равен $$$[1, 2, 2, 3, 5] \rightarrow [1, 2, 2, 3, 0]$$$.

Во втором наборе входных данных примера будет оптимальным совершить первую операцию над второй книжной полкой, а затем совершить вторую операцию. Таким образом, массив $$$a$$$ станет равен $$$[1, 5, 1, 5, 5] \rightarrow [1, 0, 1, 5, 5] \rightarrow [2, 2, 3, 3, 2]$$$.

В третьем наборе входных данных примера будет оптимальным совершить вторую операцию. Таким образом, массив $$$a$$$ станет равен $$$[1, 2, 5, 3, 5] \rightarrow [4, 3, 3, 3, 3]$$$.

В четвертом наборе входных данных примера будет оптимальным совершить первую операцию над первой и второй книжными полками. Таким образом, массив $$$a$$$ станет равен $$$[4, 4, 1, 1] \rightarrow [0, 0, 1, 1]$$$.

В пятом наборе входных данных примера будет оптимальным использовать вторую операцию. Таким образом, массив $$$a$$$ станет равен $$$[4, 4, 1, 1] \rightarrow [2, 3, 2, 3]$$$.