На олимпиаде по лингвистике Оле в одном из заданий попался текст на неизвестном ей языке. Внимательно изучив текст, Оля пришла к выводу, что в этом языке слова бывают двух типов: короткие и длинные. Все короткие слова состоят из $$$a$$$ букв, а все длинные слова состоят из $$$b$$$ букв ($$$a \lt b$$$). Подсчитав слова, Оля определила, что в тексте содержится $$$n$$$ различных коротких слов и $$$m$$$ различных длинных слов. У Оли хорошо получается решать задания с неизвестными языками, так что она может определить значение любого короткого слова за $$$c$$$ секунд и может определить значение любого длинного слова за $$$d$$$ секунд.
Задание олимпиады заключается в том, чтобы написать стихотворение на загадочном языке, используя в нём слова из текста. Поскольку Оля — девочка творческая, она может составить стихотворение из любого набора слов, значения которых она понимает. Оля хочет, чтобы в её стихотворении суммарно было хотя бы $$$k$$$ букв, никакое слово не встречалось более одного раза и два слова одинаковой длины не шли подряд, иначе её стихотворение выйдет слишком скучным.
Посчитайте минимальное время, за которое Оля может определить значения необходимых ей для написания стихотворения слов.
В первой строке вводятся два натуральных числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 10^{18}, 1 \le m \le 10^{18} $$$) — количество различных коротких и длинных слов в тексте, данном в задании, соответственно.
Во второй строке вводится два натуральных числа $$$a$$$ и $$$b$$$ ($$$1 \le a \lt b \le 10^{18} $$$) — длина короткого и длинного слова соответственно.
В третьей строке вводятся два натуральных числа $$$c$$$ и $$$d$$$ ($$$1 \le c \le 10^6, 1 \le d \le 10^6 $$$) — время в секундах, которое потребуется Оле для определения значений одного короткого и одного длинного слова соответственно.
В четвёртой строке вводится натуральное число $$$k$$$ ($$$1 \le k \le 10^{12}$$$) — минимальное суммарное количество букв, которое должно содержать Олино стихотворение.
Если у Оли не получится составить стихотворение, соответствующее условиям, выведите $$$-1$$$. Иначе выведите минимальное время в секундах, которое ей понадобится на определение значений слов на таинственном языке для написания стихотворения.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
Обратите внимание, что подзадачи 1, 2 и 3 не требуют прохождения тестов из условия.
| Подзадача | Баллы | Доп. ограничения | Необх. подзадачи | Комментарий |
| 0 | 0 | – | – | Тесты из условия |
| 1 | 10 | $$$n = m = k$$$ и $$$c \geq d$$$ | – | – |
| 2 | 10 | $$$n \leq m$$$ и $$$c \geq d$$$ | 1 | – |
| 3 | 20 | $$$n = m = k$$$ | 1 | – |
| 4 | 20 | $$$k \leq 10^4$$$ | 0 | – |
| 5 | 40 | – | 0, 1, 2, 3, 4 | – |
4 23 510 118
32
4 33 510 118
23
4 23 510 120
-1
4 23 51 1018
23
2 23 51 1013
21
Обратите внимание, что числа во входных данных и ответ могут быть больше, чем максимальное возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C и C++, тип long в Java и C#). Язык Python будет корректно работать и с типом int.
Обозначим короткое слово за «К», а длинное слово — за «Д».
В первом примере Оле выгоднее всего определить значения трёх коротких слов и двух длинных слов. Это займёт у Оли суммарно $$$3 \cdot 10 + 2 \cdot 1 = 32 $$$ секунды. В этом случае Олино стихотворение будет иметь следующий формат: КДКДК
Во втором примере Оле выгоднее всего определить значения двух коротких слов и трёх длинных слов. Это займёт у Оли суммарно $$$2 \cdot 10 + 3 \cdot 1 = 23 $$$ секунды. В этом случае Олино стихотворение будет иметь следующий формат: ДКДКД
В третьем примере Оля не может составить стихотворение, соответствующее всем ограничениям.
