A13676 | 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?

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.

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.