Game of Gnomes

Time limit1sMemory limit512 MB

Summary

Split n gnomes into at most m groups so that the enemy's bolts, each killing k gnomes from one group per turn, let you deal the most total damage.

Level: Medium7 of 10
Topics: Math, Greedy
Solved: No attempts yet

Problem

The enemy and their massive army are approaching your fortress, and the only defense is a legion of guardian gnomes. Winning is hopeless, so the goal is to deal as much damage to the enemy as possible.

You have $n$ gnomes. Before the battle, you divide them into at most $m$ non-empty groups. The battle proceeds in turns. Each turn, the gnomes attack and deal one unit of damage for each living gnome. Then the enemy throws a lightning bolt at one of the $m$ groups. The bolt kills $k$ gnomes in that group, or all of them if the group has fewer than $k$ living gnomes. The battle ends when all gnomes are dead. The enemy always throws the bolts optimally, so that the total damage is minimized.

What is the maximum total damage you can deal to the enemy if you divide the gnomes into groups optimally?

Input

A single line contains three integers $n$ , $m$ , and $k$ ( $1 \le n \le 10^9$ , $1 \le m, k \le 10^7$ ).

Output

Print the maximum amount of damage you can cause to the enemy.

Examples2

Example 1
Input
```
10 4 3
```
Expected output
```
27
```
Example 2
Input
```
5 10 100
```
Expected output
```
15
```