CF1413E.Solo mid Oracle

Meka-Naruto plays a computer game. His character has the following ability: given an enemy hero, deal $a$ instant damage to him, and then heal that enemy $b$ health points at the end of every second, for exactly $c$ seconds, starting one second after the ability is used. That means that if the ability is used at time $t$, the enemy's health decreases by $a$ at time $t$, and then increases by $b$ at time points $t + 1$, $t + 2$, ..., $t + c$ due to this ability.

The ability has a cooldown of $d$ seconds, i. e. if Meka-Naruto uses it at time moment $t$, next time he can use it is the time $t + d$. Please note that he can only use the ability at integer points in time, so all changes to the enemy's health also occur at integer times only.

The effects from different uses of the ability may stack with each other; that is, the enemy which is currently under $k$ spells gets $k\cdot b$ amount of heal this time. Also, if several health changes occur at the same moment, they are all counted at once.

Now Meka-Naruto wonders if he can kill the enemy by just using the ability each time he can (that is, every $d$ seconds). The enemy is killed if their health points become $0$ or less. Assume that the enemy's health is not affected in any way other than by Meka-Naruto's character ability. What is the maximal number of health points the enemy can have so that Meka-Naruto is able to kill them?

Meka-Naruto 正在玩一款电脑游戏。他的角色拥有如下技能：对一名敌方英雄，立即造成 $a$ 点伤害；随后，从该技能施放后 1 秒起，每秒为其恢复 $b$ 点生命值，持续恰好 $c$ 秒。也就是说，若该技能在时刻 $t$ 施放，则敌方英雄的生命值在时刻 $t$ 立即减少 $a$，并在时刻 $t + 1$、$t + 2$、…、$t + c$ 分别因该次技能而增加 $b$ 点生命值。

该技能具有 $d$ 秒的冷却时间：若 Meka-Naruto 在时刻 $t$ 施放该技能，则下一次可施放的时间为 $t + d$。注意，他只能在整数时刻施放技能，因此所有对敌方英雄生命值的影响也仅发生在整数时刻。

不同次施放的技能效果可以叠加：若某敌方英雄当前正受到 $k$ 个该技能效果的影响，则其在当前时刻将获得 $k \cdot b$ 点治疗量。此外，若同一时刻发生多次生命值变化，则所有变化均同时生效。

现在 Meka-Naruto 想知道：若他每次冷却一结束就立即施放该技能（即每隔 $d$ 秒施放一次），能否击杀该敌方英雄？当敌方英雄的生命值降至 $0$ 或更低时即被击杀。假设敌方英雄的生命值不受 Meka-Naruto 角色技能以外的任何因素影响。那么，在保证 Meka-Naruto 能够击杀敌方英雄的前提下，该敌方英雄初始生命值的最大可能值是多少？

The first line contains an integer $t$ ($1\leq t\leq 10^5$) standing for the number of testcases.

Each test case is described with one line containing four numbers $a$, $b$, $c$ and $d$ ($1\leq a, b, c, d\leq 10^6$) denoting the amount of instant damage, the amount of heal per second, the number of heals and the ability cooldown, respectively.

第一行包含一个整数 $t$（$1\leq t\leq 10^5$），表示测试用例的数量。

每个测试用例由一行描述，该行包含四个数字 $a$、$b$、$c$ 和 $d$（$1\leq a, b, c, d\leq 10^6$），分别表示瞬时伤害量、每秒治疗量、治疗次数和技能冷却时间。

For each testcase in a separate line print $-1$ if the skill can kill an enemy hero with an arbitrary number of health points, otherwise print the maximal number of health points of the enemy that can be killed.

对于每个测试用例，在单独一行中输出 $-1$（如果该技能可以击杀任意生命值的敌方英雄），否则输出可击杀的敌方英雄的最大生命值。

In the first test case of the example each unit of damage is cancelled in a second, so Meka-Naruto cannot deal more than 1 damage.

In the fourth test case of the example the enemy gets:

• $4$ damage ($1$-st spell cast) at time $0$;
• $4$ damage ($2$-nd spell cast) and $3$ heal ($1$-st spell cast) at time $1$ (the total of $5$ damage to the initial health);
• $4$ damage ($3$-nd spell cast) and $6$ heal ($1$-st and $2$-nd spell casts) at time $2$ (the total of $3$ damage to the initial health);
• and so on.

One can prove that there is no time where the enemy gets the total of $6$ damage or more, so the answer is $5$. Please note how the health is recalculated: for example, $8$-health enemy would not die at time $1$, as if we first subtracted $4$ damage from his health and then considered him dead, before adding $3$ heal.

In the sixth test case an arbitrarily healthy enemy can be killed in a sufficient amount of time.

In the seventh test case the answer does not fit into a 32-bit integer type.

在示例的第一个测试用例中，每单位伤害均在一秒内被抵消，因此 Meka-Naruto 无法造成超过 1 点伤害。

在示例的第四个测试用例中，敌人受到的伤害/治疗情况如下：

• 在时刻 $0$：受到 $4$ 点伤害（第 $1$ 个法术施放）；
• 在时刻 $1$：受到 $4$ 点伤害（第 $2$ 个法术施放）并获得 $3$ 点治疗（第 $1$ 个法术施放），对初始生命值造成的净伤害为 $5$ 点；
• 在时刻 $2$：受到 $4$ 点伤害（第 $3$ 个法术施放）并获得 $6$ 点治疗（第 $1$ 和第 $2$ 个法术施放），对初始生命值造成的净伤害为 $3$ 点；
• 依此类推。

可以证明：不存在任何时刻使得敌人受到的累计净伤害达到或超过 $6$ 点，因此答案为 $5$。请注意生命值的重新计算方式：例如，一个初始生命值为 $8$ 的敌人在时刻 $1$ 不会死亡；因为必须先扣除 $4$ 点伤害，再叠加 $3$ 点治疗，最后才判断其是否死亡（即不能在加治疗前就因生命值 ≤ 0 而判定死亡）。

在第六个测试用例中，无论敌人初始生命值多高，只要给予足够长的时间，总能将其击杀。

在第七个测试用例中，答案无法用 32 位整数类型表示。