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

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

Армия жителей Средиземья будет состоять из нескольких отрядов. Известно, что каждая пара существ одной расы, которые находятся в разных отрядах, прибавляет $$$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 0
1 2 3
Выходные данные
4
Входные данные
3 5 10
2 5 3
Выходные данные
40

Примечание

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

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