Трансфер жизни
Трансфер жизни
Примечание: "фели" - это местная валюта.
В великом городе Некорешть проживает n человек, для которых мы знаем их возраст: ai
- это возраст i-го человека. Сейчас они в отпуске, поэтому решили съездить в Писиев, посетить знаменитый музей Кошксеум. Ехать можно как на машине, так и на мотоцикле:
- автомобиль может перевозить k человек (один водитель должен быть не моложе
lc
лет и k - 1 пассажиров). Стоимость аренды автомобиля составляетpc
фели. - мотоцикл может перевозить только одного человека (ему должно быть не менее
1m
лет). Стоимость аренды мотоциклаpm
фели.
К сожалению, у людей проблемы с деньгами, поэтому они решили посоветоваться с Мьюлином, великим местным фокусником из города. Используя мощное заклинание Мукадабра, Мьюлин может переносить возраст с одного человека на другого. Формально он может уменьшить возраст x человека и увеличить возраст y другого человека на ту же величину (поэтому сумма возрастов постоянна). Стоимость переноса 1 единицы возраста составляет t фели. По магическим медицинским причинам возраст человека не может быть изменен более чем на d лет (если исходный возраст x, его возраст должен быть не менее x - d и не более x + d в любое время). Кроме того, возраст не может быть ниже 1 года.
Помогите жителям Некорешть потратить как можно меньше денег, чтобы они смогли добраться до Писиева.
Входные данные
В первой строке записаны два целых числа n и k (1 ≤ n, k ≤ 105
) - количество людей и максимальное количество человек, которое может находиться в одной машине.
Вторая строка содержит четыре целых числа lc
, pc
, lm
и pm
(1 ≤ lm
< lc
≤ 105
, 1 ≤ pm
< pc
≤ 105
) - минимальный возраст для вождения автомобиля; цена аренды одного автомобиля; минимальный возраст для вождения мотоцикла и стоимость аренды одного мотоцикла.
В третьей строке записаны два целых числа t и d (0 ≤ t, d ≤ 105
) - стоимость переноса одного года и максимальное количество раз, которое заклинания могут быть применены на каждого человека.
Четвертая строка содержит n целых чисел a1
, a2
, ..., an
(1 ≤ ai
≤ 105
) - возраст i-го человека.
Выходные данные
Выведите одно число - наименьшее количество фели, которое люди должны потратить, чтобы добраться до своей цели назначения. Если такого решения нет, выведите -1.
2 2 18 1000 16 1 5 3 16 15
1010
2 2 23 10 15 5 2 2 9 20
-1