Problem A. Gorn

Input file:input.txt   Time limit:1 sec
Output file:output.txt   Memory limit:256 Mb
Maximum points:100  

Statement

Wilhelm plays Gorn game in virtual reality, fighting against N gladiators on the arena. He has a bow and an infinite number of arrows and never misses an enemy with a shot.

When Wilhelm hits an enemy gladiator for the first time, he inflicts D points of damage, so gladiator loses D hit points. Every following hit on the same gladiator increases damage by K points due to weakening of the gladiator's armor. When hitting a new gladiator, damage again starts with D and increases after each hit. Gladiator dies when his hit points become zero or negative.

What is the minimum number of arrows Wilhelm must spend to kill all gladiators?

Constraints

1 ≤ N ≤ 104

1 ≤ D≤ 105

1 ≤ K ≤ 103

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
4 1 1
1 2 3 4
8

0.034s 0.007s 15