Трансфер життя
Примітка: "фелі" - це місцева валюта.
У великому місті Некорешть проживає n осіб, для яких ми знаємо їхній вік: a[i] - це вік i-ї особи. Зараз вони у відпустці, тому вирішили поїхати в Писіїв, відвідати знаменитий музей Кошксеум. Їхати можна як на машині, так і на мотоциклі:
автомобіль може перевозити k осіб (один водій повинен бути не молодше
l[c]років і k - 1 пасажирів). Вартість оренди автомобіля становитьp[c]фелі.мотоцикл може перевозити тільки одну особу (їй повинно бути не менше
l[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.