You have $$n$$ stacks of gold coins, with $$n$$ coins in each stack. The coins appear identical, but you know that all the coins in one stack are counterfeit. You know the weight of a genuine coin and you know the weight of genuine and counterfeit coins differs exactly 1 gram (you have no idea which one is the lightest). What is the minimal number of weighings needed to find the counterfeit stack?
A single weighing is sufficient. Take one coin from the first stack, two from the second stack, three from the third stack, and so on up to and including all coins from the last stack. These are \[ 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2} \] gold coins in total. Weigh this collection together. The difference between the measured weight and the weight of the coins if all of them were genuine corresponds to the number of coins you have taken from the counterfeit stack.
Input
Three strictly positive integers, each on a separate line:
-
the number of stacks (and also the number of gold coins in each stack)
-
the weight of a genuine gold coin (in gram)
-
the weight of all gold coins (in gram) that are weighed together when you apply the weighing strategy outlined in the introduction
Output
A single line containing the number of gold coins that you have taken from the counterfeit stack when applying the weighing strategy outlined in the introduction.
Example
Input:
10
1
60Output:
5