Solo mid Oracle
Contest: Technocup 2021 - Elimination Round 1
Difficulty rating: 2100
Tags: greedy, math, ternary search

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?

Input format:
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.

Output format:
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.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
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

Example output:
1
2
1
5
534
-1
500000500000

Editorial:
It will be easier to explain using illustrations. We will use timelines, where each cast spell instance will occupy a separate row; and each second will be represented as a column.
First of all, if $$$a > b\cdot c$$$ then the answer is $$$-1$$$. Indeed, after time $$$t$$$ the total amount of damage dealt is $$$(a - bc)$$$ for each spell which has expired completely plus some damage from spells which have not expired. The first summand can be as great as we want it to, and the second one is bounded by, say, $$$-bc^2$$$ as there are at most $$$c$$$ spells which have not yet expired, and each of them healed the enemy by at most $$$b$$$ units each second, for at most $$$c$$$ seconds. Therefore, the damage may be arbitrarily huge.
On the other hand, if $$$a\leq bc$$$, then the answer always exists, and here is why. First of all, let's only look at the moments divisible by $$$d$$$ — that is, the moments when damage was dealt. It is obvious that for every other moment $$$t$$$ the enemy had less (or the same amount of) health at time $$$t-1$$$. Second, if $$$t\geq c$$$, then the enemy had no more health than now at the moment $$$t-d$$$. Indeed, the difference between damages then and now is exactly one full-lasted spell, which is non-negative, as we know. For clarity take a look at the pictures below:
So now we know that we may consider only $$$t < c$$$, and it follows in particular that the answer exists. Also, when in general should we subtract $$$d$$$ from $$$t$$$ to obtain a more damaged enemy? One can see that if $$$t < c$$$ then the damage we subtract is $$$a - tb$$$, and since $$$t = dk$$$ for some integer nonnegative $$$k$$$, then we subtract $$$a - bdk$$$ damage. It makes sense to do this while $$$a - bdk < 0$$$:
In other words, we have reduced the task to the following: find the greatest $$$k$$$ so that $$$a \geq bdk$$$, and cast the spell $$$(k+1)$$$ time. The enemy will have the least amount of health just after we cast the spell for the $$$(k+1)$$$-st time. The answer is thus $$$a(k+1) - \dfrac{k(k+1)}{2}bd$$$. The time complexity of this solution is $$$O(1)$$$ per test.
One could also find out that the enemy's health is convex over time and use ternary search to find the minimum. It requires $$$O(\log{maxanswer})$$$ per test, which is still ok.