Solo mid Oracle

题意翻译

你在打游戏。有一个敌人,它有一个初始生命。 + 你每次可以发起进攻，使得敌人的生命值 $-a$。 + 敌人会恢复生命，如果你在 $t$ 时刻发起进攻 $t+1,t+2,\cdots,t+c$ 时刻敌人可以恢复生命 $b$。 + 你的进攻需要“冷却”，如果你在 $t$ 时刻发起进攻，下一次进攻需要在 $t+d$ 时刻。 敌人生命值减少和恢复都在同一时刻进行。如果在任意时刻敌人的生命值 $\le 0$ ，你就赢了。 问敌人最大有多少初始生命时，你可以获胜。如果答案为无穷大，则输出 $-1$。$t$ 组数据。 $1\le t\le 100000,1\le a,b,c,d\le 1000000000$。

题目描述

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.

输入输出样例

输入样例 #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

1
2
1
5
534
-1
500000500000

说明

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.