Поликарп провел целый день за подготовкой задач для вас. Теперь ему нужно поспать хотя бы \(a\) минут, чтобы отдохнуть.
Поликарп может проснуться только от звука будильника. Он только заснул, а его первый будильник прозвонит ровно через \(b\) минут.
Каждый раз когда Поликарп просыпается, он решает, заводить ли будильник еще раз или нет. Если он проспал меньше \(a\) минут суммарно, то он заводит будильник так, чтобы тот прозвонил ровно через \(c\) минут, и тратит \(d\) минут, чтобы снова заснуть. Иначе же он встает с кровати, начиная новый день.
Если будильник звонит, пока Поликарп все еще засыпает, то он снова его заводит на \(c\) минут и опять тратит \(d\) минут, чтобы заснуть.
Вам же всего лишь предстоит выяснить, когда Поликарп встанет с кровати или сообщить, что это не случится никогда.
Пожалуйста, прочитайте пояснение, чтобы получше понять пример.
Выходные данные
На каждый набор входных данных выведите одно целое число. Если Поликарп никогда не встанет с кровати, то выведите -1. Иначе выведите время, которое Поликарп потратит до того, как встать с кровати.
Примечание
В первом наборе входных данных Поликарп просыпается через \(3\) минуты. Он отдохнул только \(3\) минуты из необходимых \(10\). Поэтому он снова заводит будильник, чтобы тот прозвенел через \(6\) минут, и тратит \(4\) минуты, чтобы уснуть. То есть он отдыхает в течение еще \(2\) минут, что суммируется в \(3+2=5\) минут сна. Он повторяет эту процедуру еще три раза, и получается \(11\) минут сна. Наконец, он встает с кровати. Он потратил \(3\) минуты до первого будильника, в потом заново завел будильник четыре раза. Ответ равен \(3+4 \cdot 6 = 27\).
Второй набор входных данных похож на первый, но Поликарпу надо \(11\) минут, чтобы выспаться, вместо \(10\). Однако, это ничего не меняет, потому что Поликарп получает \(11\) минут сна при таких настройках будильника так и так.
В третьем наборе входных данных Поликарп просыпается достаточно отдохнувшим уже после первого будильника. Поэтому ответ равен \(b=9\).
В четвертом наборе входных данных Поликарп просыпается через \(5\) минут. К сожалению, дальше он не может отдохнуть ни минуты, заводя будильник все снова и снова бесконечно :(
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
10 3 6 4
11 3 6 4
5 9 4 10
6 5 2 3
1 1 1 1
3947465 47342 338129 123123
234123843 13 361451236 361451000
|
27
27
9
-1
1
6471793
358578060125049
|