D. Медвежонок и вклад
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Codeforces — замечательная платформа, одной из её особенностей является возможность посмотреть вклад того или иного участника в развитие сообщества. У каждого зарегистрированного пользователя есть параметр вклад — целое число, не обязательно положительное. Всего зарегистрировано n участников, вклад i-го из них равен ti.

Маленький полярный медвежонок Лимак только начала заниматься спортивным программированием. У него ещё даже нет своего аккаунта на Codeforces, но он уже может ставить плюсы записям в блогах и комментариям. Минусы Лимак никогда не использует. В рамках данной задачи можно считать, что у каждого зарегистрированного пользователя бесконечно много комментариев и записей в блоге.

  • Лимак может потратить b минут на чтение блога и поставить ему плюс. Вклад автора блога увеличивается на 5.
  • Лимак может потратить c минут на чтение комментария и поставить ему плюс. Вклад автора комментария увеличивается на 1.

Обратите внимание, что возможны входных данные в которых Лимак читает блоги быстрее, чем комментарии.

Лимак очень любит ничьи. Он хотел бы, чтобы у каких-нибудь k пользователей была ничья по вкладу. То есть он собирается прочитать сколько-то блогов и сколько-то комментариев и поставить им плюсы, чтобы в результате существовало целое число x, такое что как вклад как минимум k зарегистрированных пользователей равен в точности x.

Сколько минимум времени придётся потратить Лимаку, чтобы добиться желаемого?

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

В первой строке входных данных записаны четыре целых числа n, k, b и c (2 ≤ k ≤ n ≤ 200 000, 1 ≤ b, c ≤ 1000) — количество зарегистрированных пользователей, количество пользователей в одной группе по вкладу, которого хочет добиться Лимак, время необходимое на прочтение блога и время необходимое на прочтение комментария соответственно.

Во второй строке записаны n целых чисел t1, t2, ..., tn (|ti| ≤ 109), где ti означает изначальный вклад i-го пользователя.

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

Выведите минимальное количество минут, которое придётся потратить Лимаку чтобы добиться ничьей между как минимум k пользователями.

Примеры
Входные данные
4 3 100 30
12 2 6 1
Выходные данные
220
Входные данные
4 3 30 100
12 2 6 1
Выходные данные
190
Входные данные
6 2 987 789
-8 42 -4 -65 -8 -8
Выходные данные
0
Примечание

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

  • Потратить 100 минут на чтение блога пользователя 4 и увеличить его вклад с 1 до 6.
  • Потратить 4·30 = 120 минут на чтение четырёх комментариев пользователя 2 и увеличить его вклад с 2 до 6 (четыре увеличения по 1).

Таким образом Лимак потратит 100 + 4·30 = 220 минут и вклад пользователей 2, 3 и 4 будет равен 6.

Во втором примере Лимак тратит 30 минут на чтение блога и 100 минут на чтение комментария. Он может добиться того, чтобы у трёх пользователей вклад был равен 12 потратив 100 + 3·30 = 190 минут:

  • Потратив 2·30 = 60 минут на чтение двух блогов пользователя номер 2 увеличить его вклад с 2 до 12.
  • Потратив 30 + 100 минут на чтение одного блога и одно комментарий пользователя 3 увеличить его вклад с 6 до 6 + 5 + 1 = 12.