Примечание: "фели" - это местная валюта.
В великом городе Некорешть проживает n человек, для которых мы знаем их возраст: a[i]
- это возраст i-го человека. Сейчас они в отпуске, поэтому решили съездить в Писиев, посетить знаменитый музей Кошксеум. Ехать можно как на машине, так и на мотоцикле:
автомобиль может перевозить k человек (один водитель должен быть не моложе l[c]
лет и k - 1 пассажиров). Стоимость аренды автомобиля составляет p[c]
фели.
мотоцикл может перевозить только одного человека (ему должно быть не менее 1[m]
лет). Стоимостьаренды мотоцикла p[m]
фели.
К сожалению, у людей проблемы с деньгами, поэтому они решили посоветоваться с Мьюлином, великим местным фокусником из города. Используя мощное заклинание Мукадабра, Мьюлин может переносить возраст с одного человека на другого. Формально он может уменьшить возраст x человека и увеличить возраст y другого человека на ту же величину (поэтому сумма возрастов постоянна). Стоимость переноса 1 единицы возраста составляет t фели. По магическим медицинским причинам возраст человека не может быть изменен более чем на d лет (если исходный возраст x, его возраст должен быть не менее x - d и не более x + d в любое время). Кроме того, возраст не может быть ниже 1 года.
Помогите жителям Некорешть потратить как можно меньше денег, чтобы они смогли добраться до Писиева.
В первой строке записаны два целых числа n и k (1 ≤ n, k ≤ 10^5
) - количество людей и максимальное количество человек, которое может находиться в одной машине.
Вторая строка содержит четыре целых числа l[c]
, p[c]
, l[m]
и p[m]
(1 ≤ l[m]
< l[c]
≤ 10^5
, 1 ≤ p[m]
< p[c]
≤ 10^5
) - минимальный возраст для вождения автомобиля; цена аренды одного автомобиля; минимальный возраст для вождения мотоцикла и стоимость аренды одного мотоцикла.
В третьей строке записаны два целых числа t и d (0 ≤ t, d ≤ 10^5
) - стоимость переноса одного года и максимальное количество раз, которое заклинания могут быть применены на каждого человека.
Четвертая строка содержит n целых чисел a[1]
, a[2]
, ..., a[n]
(1 ≤ a[i]
≤ 10^5
) - возраст i-го человека.
Выведите одно число - наименьшее количество фели, которое люди должны потратить, чтобы добраться до своей цели назначения. Если такого решения нет, выведите -1.