D. Подземелья Одинокой горы
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Однажды, люди, эльфы, гномы и другие жители Средиземья собрались отнять у Смога украденные у них сокровища. Во имя этой великой цели они сплотились вокруг сильного эльфа Тимофея и начали планировать свержение правителя Одинокой горы.

Армия жителей Средиземья будет состоять из нескольких отрядов. Известно, что каждая пара существ одной расы, которые находятся в разных отрядах, прибавляет $$$b$$$ единиц к суммарной силе армии. Но так как Тимофею будет сложно руководить армией, состоящей из большого числа отрядов, то суммарная сила армии, состоящей из $$$k$$$ отрядов, уменьшается на $$$(k - 1) \cdot x$$$ единиц. Обратите внимание, что армия всегда состоит из хотя бы одного отряда.

Известно, что в Средиземье проживают $$$n$$$ рас, и количество существ $$$i$$$-й расы равно $$$c_i$$$. Помогите жителям Средиземья определить максимальную силу армии, которую они могут составить.

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$b$$$ и $$$x$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le b \le 10^6, 0 \le x \le 10^9$$$)— количество рас и константы $$$b$$$ и $$$x$$$, описанные выше.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \le c_i \le 2 \cdot 10^5$$$) — количества существ каждой из $$$n$$$ рас.

Гарантируется, что сумма значений $$$c_1 + c_2 + \ldots + c_n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

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

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

В первом наборе входных данных жители Средиземья могут составить $$$3$$$ отряда. Так как $$$x = 0$$$, то сила армии не уменьшится из-за количества отрядов. Жителей по отрядам можно распределить так:

  • Единственного представителя первой расы можно отправить в первый отряд.
  • Первого представителя второй расы можно отправить в первый отряд, второго представителя второй расы можно отправить во второй отряд. Тогда суммарная сила армии увеличится на $$$b = 1$$$.
  • Первого представителя третьей расы можно отправить в первый отряд, второго представителя третьей расы можно отправить во второй отряд, третьего представителя третьей расы можно отправить в третий отряд. Тогда суммарная сила армии увеличится на $$$3 \cdot b = 3$$$, так как они образуют три пары, находящиеся в разных отрядах.

Таким образом, суммарная сила армии равна $$$4$$$.

Во втором наборе входных данных жители Средиземья могут составить $$$3$$$ отряда. Так как $$$x = 10$$$, то сила армии уменьшится на $$$20$$$. Жителей по отрядам можно распределить так:

  • Первого представителя первой расы можно отправить в первый отряд, второго представителя первой расы можно отправить во второй отряд. Тогда суммарная сила армии увеличится на $$$b = 5$$$.
  • Первого и второго представителя второй расы можно отправить в первый отряд, третьего и четвёртого представителя второй расы можно отправить во второй отряд, пятого представителя третьей расы можно отправить в третий отряд. Тогда суммарная сила армии увеличится на $$$8 \cdot b = 40$$$.
  • Первого представителя третьей расы можно отправить в первый отряд, второго представителя третьей расы можно отправить во второй отряд, третьего представителя третьей расы можно отправить в третий отряд. Тогда суммарная сила армии увеличится на $$$3 \cdot b = 15$$$, так как они образуют три пары, находящиеся в разных отрядах.

Таким образом, суммарная сила армии равна $$$5 + 40 + 15 - 20 = 40$$$.