Santa and Wages

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type

One of the primary reasons why the North Pole operates so slowly is that Santa's elves are overpaid. Santa is annoyed at this and asks you to make financial changes so that the optimal toy production speed is reached.

At their current wage, Santa has N elves that each make M toys per day. You decide to shave some money off each elf's wages and spend it instead on the number of elves hired. Each time you cut their wages, you will be able to sustain one extra elf worker but all of their speeds will decrease by one toy per day. You cannot cut their wages anymore after the toy production speeds reach 0.

You must find the optimal number of times to cut the elves' wages to maximize their total toy production speed. If there are multiple possible choices giving the same maximum, you must choose the one that would cut the wages the most. Additionally, you are allowed to choose to not cut their wages at all if it leads to the optimal speed.

Input Specification

The first line contains two space-separated integers, N and M (1 \le N, M \le 10^{12}).

Output Specification

Output one line containing the optimal number of times to cut their wages.

Note that 64-bit integers are required to pass.


Subtask 1 [30%]

1 \le N, M \le 10^6

Subtask 2 [70%]

No further constraints.

Sample Input

4 7

Sample Output


Explanation for Sample Output

If we choose to cut their wages 2 times, there will be 4+2=6 workers each working at a speed of 7-2=5 toys per day. Therefore, the total production speed will be 6 \cdot 5=30 toys per day.


There are no comments at the moment.