B. Эмоции
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В одной очень популярной коллекционной карточной онлайн-игре есть $$$n$$$ эмоций (игра довольно популярна, поэтому не будем упоминать ее название). $$$i$$$-я эмоция делает оппонента счастливее на $$$a_i$$$ единиц (все мы знаем, что эмоции в этой игре используются для того, чтобы делать оппонентов счастливее).

Вы можете использовать некоторые эмоции $$$m$$$ раз. Вы можете использовать любую эмоцию один раз, больше одного раза или не использовать вообще. Единственное ограничение заключается в том, что вы не можете использовать одну и ту же эмоцию более, чем $$$k$$$ раз подряд (иначе оппонент подумает, что вы его троллите).

Заметим, что две эмоции $$$i$$$ и $$$j$$$ ($$$i \ne j$$$) такие, что $$$a_i = a_j$$$, являются различными.

Вы хотите сделать оппонента настолько счастливым, насколько это возможно. Найдите максимально возможную величину счастья оппонента.

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

Первая строка входных данных содержит три целых числа $$$n, m$$$ и $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le k \le m \le 2 \cdot 10^9$$$) — количество эмоций, количество раз, которое вы можете использовать эмоции и максимальное количество использований одной и той же эмоции подряд.

Вторая строка входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$), где $$$a_i$$$ равно значению счастья $$$i$$$-й эмоции.

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

Выведите одно целое число — максимальное счастье оппонента при условии, что вы будете использовать эмоции так, как описано в условии задачи.

Примеры
Входные данные
6 9 2
1 3 3 7 4 2
Выходные данные
54
Входные данные
3 1000000000 1
1000000000 987654321 1000000000
Выходные данные
1000000000000000000
Примечание

В первом примере можно использовать эмоции в соответствии со следующей последовательностью: $$$4, 4, 5, 4, 4, 5, 4, 4, 5$$$.