Монокарп играет в компьютерную игру. В этой игре он управляет космическим кораблем. Его цель — уничтожить космический корабль противника.
На корабле Монокарпа установлены два лазера. Оба лазера \(1\) и \(2\) характеризуются двумя значениями:
- \(p_i\) — мощность лазера;
- \(t_i\) — время перезарядки лазера.
Когда лазер полностью заряжен, Монокарп может либо выстрелить из него, либо дождаться полной зарядки другого лазера и выстрелить из них обоих одновременно.
У корабля противника \(h\) прочности и \(s\) силы щита. Когда Монокарп стреляет по кораблю противника, тот получает \((P - s)\) урона (т. е. \((P - s)\) вычитается из его прочности), где \(P\) — это суммарная мощность лазеров, из которых выстрелил Монокарп (т. е. \(p_i\), если он стрелял только из лазера \(i\), и \(p_1 + p_2\), если он стрелял из обоих одновременно). Корабль противника считается уничтоженным, когда его прочность становится меньше или равна \(0\).
Изначально оба лазера разряжены.
За какое наименьшее время Монокарп может уничтожить корабль противника?
Выходные данные
Выведите одно целое число — наименьшее время, за которое Монокарп может уничтожить корабль противника.
Примечание
В первом примере Монокарп ждет зарядки обоих лазеров, затем стреляет из обоих в \(10\), они наносят \((5 + 4 - 1) = 8\) единиц урона. Затем он снова ждет и стреляет из обоих лазеров в \(20\), нанося еще \(8\) единиц урона.
Во втором примере Монокарп не ждет зарядки второго лазера. Он просто стреляет из первого \(25\) раз, нанося \((10 - 9) = 1\) единицу урона каждый раз.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 10
4 9
16 1
|
20
|
|
2
|
10 1
5000 100000
25 9
|
25
|