E. Oracle соло мид
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Меха-Наруто играет в компьютерную игру. У его персонажа есть следующая способность: нанести вражескому герою $$$a$$$ единиц урона, затем восполнять ему $$$b$$$ единиц здоровья в конце каждой секунды, начиная со следующей, на протяжении ровно $$$c$$$ секунд. В частности, если эта способность применяется в момент времени $$$t$$$, то здоровье врага уменьшается на $$$a$$$ в момент времени $$$t$$$, а затем увеличивается на $$$b$$$ в моменты $$$t + 1$$$, $$$t + 2$$$, ..., $$$t + c$$$.

У способности есть время перезарядки, равное $$$d$$$ секундам, то есть если Меха-Наруто применяет способность в момент времени $$$t$$$, то в следующий раз он может её применить не раньше момента $$$t + d$$$. По некоторым причинам Меха-Наруто может использовать способность только в целые моменты времени, поэтому все изменения здоровья врага также происходят в целочисленные моменты.

Эффекты от разных применений заклинания накладываются друг на друга. В частности, если вражеский герой находится под действием $$$k$$$ заклинаний, применённых ранее и ещё не истёкших, то его здоровье увеличится на $$$k\cdot b$$$. Помимо этого все изменения, которые происходят в один и тот же момент времени, учитываются одновременно.

Теперь Меха-Наруто интересно, может ли он убить своего оппонента просто применяя свою способность так часто, как только можно (то есть каждые $$$d$$$ секунд). Герой считается погибшим, если уровень его здоровья становится равным $$$0$$$ или ниже. Предположим, что здоровье вражеского персонажа не изменяется никаким образом, кроме как от применения заклинания. Какое наибольшее количество здоровья может быть у врага, чтобы Меха-Наруто мог его убить?

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

Первая строка содержит единственное число $$$t$$$ ($$$1\leq t\leq 10^5$$$) — число тестов.

Каждый тест описывается четвёркой натуральных чисел $$$a$$$, $$$b$$$, $$$c$$$ и $$$d$$$ ($$$1\leq a, b, c, d\leq 10^6$$$), записанных через пробел и означающих соответственно мгновенный урон от способности, ежесекундно восполняемый объём здоровья, время действия каждого заклинания и время перезарядки способности.

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

Для каждого теста выведите на отдельной строке $$$-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
Примечание

В первом тесте из условия любая единица урона отменяется через секунду, поэтому Меха-Наруто не может нанести больше, чем 1 единицу урона.

В четвёртом тесте из условия герой оппонента получает:

  • $$$4$$$ урона ($$$1$$$-е применение способности) в момент $$$0$$$;
  • $$$4$$$ урона ($$$2$$$-е применение способности), и $$$3$$$ единицы здоровья восполняются ($$$1$$$-е применение) в момент $$$1$$$ (всего $$$5$$$ урона к начальному уровню здоровья);
  • $$$4$$$ урона ($$$3$$$-е применение способности), и $$$6$$$ здоровья восполняется ($$$1$$$-е и $$$2$$$-е применения) в момент $$$2$$$ (всего $$$3$$$ урона к изначальному здоровью);
  • и так далее.

Можно доказать, что ни к какому моменту времени враг не получит суммарно $$$6$$$ или больше урона, поэтому ответ на этот тест есть $$$5$$$. Обратите внимание, как производится пересчёт здоровья: например, если бы у врага было $$$8$$$ здоровья, он бы не умер в момент времени $$$1$$$, как если бы мы сначала вычли из его здоровья $$$4$$$ единицы, а затем сочли бы его мёртвым, не успев добавить $$$3$$$ единицы от лечения.

В шестом тесте из условия герой со сколько угодно большим количеством здоровья рано или поздно умрёт.

В седьмом тесте из условия ответ не вмещается в 32-битный целочисленный тип.