Codeforces Round 924 (Div. 2) |
---|
Закончено |
Однажды, люди, эльфы, гномы и другие жители Средиземья собрались отнять у Смога украденные у них сокровища. Во имя этой великой цели они сплотились вокруг сильного эльфа Тимофея и начали планировать свержение правителя Одинокой горы.
Армия жителей Средиземья будет состоять из нескольких отрядов. Известно, что каждая пара существ одной расы, которые находятся в разных отрядах, прибавляет $$$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$$$.
Для каждого набора входных данных выведите одно целое число — максимальную силу армии, которую могут составить жители Средиземья.
53 1 01 2 33 5 102 5 34 3 33 2 1 24 1 04 1 4 24 1 104 1 4 2
4 40 9 13 0
В первом наборе входных данных жители Средиземья могут составить $$$3$$$ отряда. Так как $$$x = 0$$$, то сила армии не уменьшится из-за количества отрядов. Жителей по отрядам можно распределить так:
Таким образом, суммарная сила армии равна $$$4$$$.
Во втором наборе входных данных жители Средиземья могут составить $$$3$$$ отряда. Так как $$$x = 10$$$, то сила армии уменьшится на $$$20$$$. Жителей по отрядам можно распределить так:
Таким образом, суммарная сила армии равна $$$5 + 40 + 15 - 20 = 40$$$.
Название |
---|