E. FTL
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Монокарп играет в компьютерную игру. В этой игре он управляет космическим кораблем. Его цель — уничтожить космический корабль противника.

На корабле Монокарпа установлены два лазера. Оба лазера $$$1$$$ и $$$2$$$ характеризуются двумя значениями:

  • $$$p_i$$$ — мощность лазера;
  • $$$t_i$$$ — время перезарядки лазера.

Когда лазер полностью заряжен, Монокарп может либо выстрелить из него, либо дождаться полной зарядки другого лазера и выстрелить из них обоих одновременно.

У корабля противника $$$h$$$ прочности и $$$s$$$ силы щита. Когда Монокарп стреляет по кораблю противника, тот получает $$$(P - s)$$$ урона (т. е. $$$(P - s)$$$ вычитается из его прочности), где $$$P$$$ — это суммарная мощность лазеров, из которых выстрелил Монокарп (т. е. $$$p_i$$$, если он стрелял только из лазера $$$i$$$, и $$$p_1 + p_2$$$, если он стрелял из обоих одновременно). Корабль противника считается уничтоженным, когда его прочность становится меньше или равна $$$0$$$.

Изначально оба лазера разряжены.

За какое наименьшее время Монокарп может уничтожить корабль противника?

Входные данные

В первой строке записаны два целых числа $$$p_1$$$ и $$$t_1$$$ ($$$2 \le p_1 \le 5000$$$; $$$1 \le t_1 \le 10^{12}$$$) — мощность и время перезарядки первого лазера.

Во второй строке записаны два целых числа $$$p_2$$$ и $$$t_2$$$ ($$$2 \le p_2 \le 5000$$$; $$$1 \le t_2 \le 10^{12}$$$) — мощность и время перезарядки второго лазера.

В третьей строке записаны два целых числа $$$h$$$ и $$$s$$$ ($$$1 \le h \le 5000$$$; $$$1 \le s < \min(p_1, p_2)$$$) — прочность и сила щита корабля противника. Обратите внимание, что последнее ограничение подразумевает, что Монокарп всегда может уничтожить корабль противника.

Выходные данные

Выведите одно целое число — наименьшее время, за которое Монокарп может уничтожить корабль противника.

Примеры
Входные данные
5 10
4 9
16 1
Выходные данные
20
Входные данные
10 1
5000 100000
25 9
Выходные данные
25
Примечание

В первом примере Монокарп ждет зарядки обоих лазеров, затем стреляет из обоих в $$$10$$$, они наносят $$$(5 + 4 - 1) = 8$$$ единиц урона. Затем он снова ждет и стреляет из обоих лазеров в $$$20$$$, нанося еще $$$8$$$ единиц урона.

Во втором примере Монокарп не ждет зарядки второго лазера. Он просто стреляет из первого $$$25$$$ раз, нанося $$$(10 - 9) = 1$$$ единицу урона каждый раз.