Трансфер життя#11278

Трансфер життя

1 секунда

128 мегабайтів

Складна

Примітка: "фелі" - це місцева валюта.

У великому місті Некорешть проживає $n$ осіб, для яких ми знаємо їхній вік: $a_{i}$ a_i - це вік $i$ -ї особи. Зараз вони у відпустці, тому вирішили поїхати в Писіїв, відвідати знаменитий музей Кошксеум. Їхати можна як на машині, так і на мотоциклі:

автомобіль може перевозити $k$ осіб (один водій повинен бути не молодше $l_{c}$ l_c років і $k - 1$ k - 1 пасажирів). Вартість оренди автомобіля становить $p_{c}$ p_c фелі.
мотоцикл може перевозити тільки одну особу (їй повинно бути не менше $l_{m}$ l_m років). Вартість оренди мотоцикла $p_{m}$ p_m фелі.

На жаль, у людей проблеми з грошима, тому вони вирішили порадитися з Мьюліном, великим місцевим фокусником з міста. Використовуючи потужне заклинання Мукадабра, Мьюлін може переносити вік з однієї особи на іншу. Формально він може зменшити вік $x$ особи і збільшити вік $y$ іншої особи на ту ж величину (тому сума віків постійна). Вартість переносу $1$ одиниці віку становить $t$ фелі. З магічних медичних причин вік особи не може бути змінений більше ніж на $d$ років (якщо початковий вік $x$ , його вік повинен бути не менше $x - d$ x - d і не більше $x + d$ x + d у будь-який час). Крім того, вік не може бути нижче $1$ року.

Допоможіть жителям Некорешть витратити якомога менше грошей, щоб вони змогли дістатися до Писіїва.

Вхідні дані

У першому рядку записані два цілих числа $n$ і $k$ ( $1 \leq n, k \leq 1 0^{5}$ 1 \leq n, k \leq 10^5) - кількість людей і максимальна кількість осіб, яка може перебувати в одній машині.

Другий рядок містить чотири цілі числа $l_{c}$ l_c, $p_{c}$ p_c, $l_{m}$ l_m і $p_{m}$ p_m ( $1 \leq l_{m} < l_{c} \leq 1 0^{5}$ 1 \leq l_m < l_c \leq 10^5, $1 \leq p_{m} < p_{c} \leq 1 0^{5}$ 1 \leq p_m < p_c \leq 10^5) - мінімальний вік для водіння автомобіля; ціна оренди одного автомобіля; мінімальний вік для водіння мотоцикла і вартість оренди одного мотоцикла.

У третьому рядку записані два цілі числа $t$ і $d$ ( $0 \leq t, d \leq 1 0^{5}$ 0 \leq t, d \leq 10^5) - вартість переносу одного року і максимальна кількість разів, яку заклинання можуть бути застосовані до кожної особи.

Четвертий рядок містить $n$ цілих чисел $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \ldots, a_n ( $1 \leq a_{i} \leq 1 0^{5}$ 1 \leq a_i \leq 10^5) - вік $i$ -ї особи.

Вихідні дані

Виведіть одне число - найменшу кількість фелі, яку люди повинні витратити, щоб дістатися до своєї мети. Якщо такого рішення немає, виведіть $- 1$ .

Приклади

Приклад 1

Приклад 2