Codeforces — замечательная платформа, одной из её особенностей является возможность посмотреть вклад того или иного участника в развитие сообщества. У каждого зарегистрированного пользователя есть параметр вклад — целое число, не обязательно положительное. Всего зарегистрировано n участников, вклад i-го из них равен ti.
Маленький полярный медвежонок Лимак только начала заниматься спортивным программированием. У него ещё даже нет своего аккаунта на Codeforces, но он уже может ставить плюсы записям в блогах и комментариям. Минусы Лимак никогда не использует. В рамках данной задачи можно считать, что у каждого зарегистрированного пользователя бесконечно много комментариев и записей в блоге.
- Лимак может потратить b минут на чтение блога и поставить ему плюс. Вклад автора блога увеличивается на 5.
- Лимак может потратить c минут на чтение комментария и поставить ему плюс. Вклад автора комментария увеличивается на 1.
Обратите внимание, что возможны входных данные в которых Лимак читает блоги быстрее, чем комментарии.
Лимак очень любит ничьи. Он хотел бы, чтобы у каких-нибудь k пользователей была ничья по вкладу. То есть он собирается прочитать сколько-то блогов и сколько-то комментариев и поставить им плюсы, чтобы в результате существовало целое число x, такое что как вклад как минимум k зарегистрированных пользователей равен в точности x.
Сколько минимум времени придётся потратить Лимаку, чтобы добиться желаемого?
Выходные данные
Выведите минимальное количество минут, которое придётся потратить Лимаку чтобы добиться ничьей между как минимум k пользователями.
Примечание
В первом примере имеется четыре зарегистрированных пользователя и Лимак хочет, чтобы была ничья между как минимум тремя из них. Оптимальный ответ можно получить следующим образом:
- Потратить 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.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 3 100 30
12 2 6 1
|
220
|
|
2
|
4 3 30 100
12 2 6 1
|
190
|
|
3
|
6 2 987 789
-8 42 -4 -65 -8 -8
|
0
|