Автобус курсирует по координатной прямой Ox от точки x = 0 до точки x = a. Выехав из точки x = 0, он доезжает до точки x = a, сразу разворачивается и едет обратно в точку x = 0. Вернувшись в точку x = 0, он сразу снова едет в точку x = a и так далее. Таким образом, автобус курсирует от x = 0 до x = a и обратно. Переезд из точки x = 0 в x = a или из точки x = a в x = 0 называется рейсом автобуса. Всего автобус должен совершить k рейсов.
Бензобак автобуса вмещает b литров бензина. На преодоление единицы расстояния автобус тратит ровно один литр бензина. Свой путь автобус начинает с полным бензобаком.
Между x = 0 и x = a в точке x = f находится заправка. Других заправок на пути автобуса нет. Проезжая мимо заправки в любом из двух направлений, автобус может остановиться и пополнить запас бензина в бензобаке. Таким образом, после остановки на заправку в бензобаке автобуса будет b литров бензина.
Какое минимальное количество раз автобус должен дозаправиться в точке x = f, чтобы начав путь в точке x = 0 совершить k рейсов?
Выходные данные
Выведите минимальное количество дозаправок автобуса, которые необходимы, чтобы совершить k рейсов. Если автобус не сможет совершить k рейсов, выведите -1.
Примечание
В первом примере автобус вынужден дозаправляться на каждом рейсе.
Во втором примере автобус может проехать без дозаправки 10 единиц расстояния. Это соответствует тому, что автобус проехал весь первый рейс, а затем 4 единицы расстояния второго рейса и оказался на заправке. Он может дозаправиться, закончить второй рейс и проехать 2 единицы расстояния от третьего рейса. В этом случае он снова окажется на заправке. Затем он может заполнить бак до 10 литров, закончить третий рейс и проехать полностью четвертый рейс. В конце пути у автобуса будет пустой бак.
В третьем примере автобус не может проехать все 3 рейса, так как если он заправится на втором рейсе, в баке будет только 5 литров бензина, а до следующей возможности заправиться автобус должен проехать 8 единиц расстояния.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 9 2 4
|
4
|
|
2
|
6 10 2 4
|
2
|
|
3
|
6 5 4 3
|
-1
|