Однажды люди, эльфы, гномы и другие жители Средиземья собрались отнять у Смога украденные у них сокровища. Во имя этой великой цели они сплотились вокруг сильного эльфа Тимофея и начали планировать свержение правителя Одинокой горы.
Армия жителей Средиземья будет состоять из нескольких отрядов. Известно, что каждая пара существ одной расы, которые находятся в разных отрядах, прибавляет $$$b$$$ единиц к суммарной силе армии. Но так как Тимофею будет сложно руководить армией, состоящей из большого числа отрядов, то суммарная сила армии, состоящей из $$$k$$$ отрядов, уменьшается на $$$(k - 1) \cdot X$$$ единиц. Обратите внимание, что армия всегда состоит из хотя бы одного отряда.
Известно, что в Средиземье проживают $$$n$$$ рас, и количество существ $$$i$$$-й расы равно $$$c_i$$$. Помогите жителям Средиземья определить максимальную силу армии, которую они могут составить.
Первая строка входных данных содержит три целых числа $$$n$$$, $$$b$$$ и $$$X$$$ ($$$1 \le n \le 200\,000$$$, $$$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 200\,000$$$) — количество существ каждой из $$$n$$$ рас.
Гарантируется, что $$$c_1 + c_2 + \ldots + c_n \le 200\,000$$$.
Выведите одно целое число — максимальную силу армии, которую могут составить жители Средиземья.
Обратите внимание, что ответ может быть больше, чем возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C и C++, тип long в Java и C#). Язык Python будет корректно работать.
В данной задаче $$$50$$$ тестов, помимо тестов из условия. Результаты работы ваших решений на всех тестах будут доступны сразу во время соревнования.
Решения, корректно работающие при $$$X = 0$$$, наберут не менее $$$16$$$ баллов.
Решения, корректно работающие при $$$n = 1$$$, наберут не менее $$$10$$$ баллов.
Решения, корректно работающие при $$$n \le 2$$$, наберут не менее $$$20$$$ баллов.
Решения, корректно работающие при $$$c_1 = c_2 = \ldots = c_n$$$, наберут не менее $$$14$$$ баллов.
Решения, корректно работающие при $$$c_1 + c_2 + \ldots + c_n \leq 2000$$$, наберут не менее $$$18$$$ баллов.
3 1 01 2 3
4
3 5 102 5 3
40
В первом примере жители Средиземья могут составить $$$3$$$ отряда. Так как $$$X = 0$$$, то сила армии не уменьшится из-за количества отрядов. Далее жителей по отрядам можно распределить так:
Таким образом, суммарная сила армии равна $$$4$$$.