В одной очень популярной коллекционной карточной онлайн-игре есть \(n\) эмоций (игра довольно популярна, поэтому не будем упоминать ее название). \(i\)-я эмоция делает оппонента счастливее на \(a_i\) единиц (все мы знаем, что эмоции в этой игре используются для того, чтобы делать оппонентов счастливее).
Вы можете использовать некоторые эмоции \(m\) раз. Вы можете использовать любую эмоцию один раз, больше одного раза или не использовать вообще. Единственное ограничение заключается в том, что вы не можете использовать одну и ту же эмоцию более, чем \(k\) раз подряд (иначе оппонент подумает, что вы его троллите).
Заметим, что две эмоции \(i\) и \(j\) (\(i \ne j\)) такие, что \(a_i = a_j\), являются различными.
Вы хотите сделать оппонента настолько счастливым, насколько это возможно. Найдите максимально возможную величину счастья оппонента.
Выходные данные
Выведите одно целое число — максимальное счастье оппонента при условии, что вы будете использовать эмоции так, как описано в условии задачи.
Примечание
В первом примере можно использовать эмоции в соответствии со следующей последовательностью: \(4, 4, 5, 4, 4, 5, 4, 4, 5\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 9 2
1 3 3 7 4 2
|
54
|
|
2
|
3 1000000000 1
1000000000 987654321 1000000000
|
1000000000000000000
|