Меха-Наруто играет в компьютерную игру. У его персонажа есть следующая способность: нанести вражескому герою \(a\) единиц урона, затем восполнять ему \(b\) единиц здоровья в конце каждой секунды, начиная со следующей, на протяжении ровно \(c\) секунд. В частности, если эта способность применяется в момент времени \(t\), то здоровье врага уменьшается на \(a\) в момент времени \(t\), а затем увеличивается на \(b\) в моменты \(t + 1\), \(t + 2\), ..., \(t + c\).
У способности есть время перезарядки, равное \(d\) секундам, то есть если Меха-Наруто применяет способность в момент времени \(t\), то в следующий раз он может её применить не раньше момента \(t + d\). По некоторым причинам Меха-Наруто может использовать способность только в целые моменты времени, поэтому все изменения здоровья врага также происходят в целочисленные моменты.
Эффекты от разных применений заклинания накладываются друг на друга. В частности, если вражеский герой находится под действием \(k\) заклинаний, применённых ранее и ещё не истёкших, то его здоровье увеличится на \(k\cdot b\). Помимо этого все изменения, которые происходят в один и тот же момент времени, учитываются одновременно.
Теперь Меха-Наруто интересно, может ли он убить своего оппонента просто применяя свою способность так часто, как только можно (то есть каждые \(d\) секунд). Герой считается погибшим, если уровень его здоровья становится равным \(0\) или ниже. Предположим, что здоровье вражеского персонажа не изменяется никаким образом, кроме как от применения заклинания. Какое наибольшее количество здоровья может быть у врага, чтобы Меха-Наруто мог его убить?
Выходные данные
Для каждого теста выведите на отдельной строке \(-1\), если способность может рано или поздно убить любого врага, каким бы большим ни был его уровень здоровья; в противном случае выведите наибольшее число здоровья, при котором оппонент будет убит.
Примечание
В первом тесте из условия любая единица урона отменяется через секунду, поэтому Меха-Наруто не может нанести больше, чем 1 единицу урона.
В четвёртом тесте из условия герой оппонента получает:
- \(4\) урона (\(1\)-е применение способности) в момент \(0\);
- \(4\) урона (\(2\)-е применение способности), и \(3\) единицы здоровья восполняются (\(1\)-е применение) в момент \(1\) (всего \(5\) урона к начальному уровню здоровья);
- \(4\) урона (\(3\)-е применение способности), и \(6\) здоровья восполняется (\(1\)-е и \(2\)-е применения) в момент \(2\) (всего \(3\) урона к изначальному здоровью);
- и так далее.
Можно доказать, что ни к какому моменту времени враг не получит суммарно \(6\) или больше урона, поэтому ответ на этот тест есть \(5\). Обратите внимание, как производится пересчёт здоровья: например, если бы у врага было \(8\) здоровья, он бы не умер в момент времени \(1\), как если бы мы сначала вычли из его здоровья \(4\) единицы, а затем сочли бы его мёртвым, не успев добавить \(3\) единицы от лечения.
В шестом тесте из условия герой со сколько угодно большим количеством здоровья рано или поздно умрёт.
В седьмом тесте из условия ответ не вмещается в 32-битный целочисленный тип.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
1 1 1 1
2 2 2 2
1 2 3 4
4 3 2 1
228 21 11 3
239 21 11 3
1000000 1 1000000 1
|
1
2
1
5
534
-1
500000500000
|