Problem description
Johnny wants to buy a lot of potatoes. He would like to find out if he is not cheated by the seller and if the bag truly contains exactly N kilograms of potatoes as declared.
The problem is that Johnny only has a simple balance weighing scale and an infinite number of A and B kilograms masses. Johnny wants to put potatoes on the left arm and put masses on the left or right arms to make the arms balanced. This could take ages – help Johnny find a way to check the weight of the potatoes using the smallest number of masses.
Write a program that: reads the weights of masses that Johnny has and the declared weight of potatoes, finds the smallest number of masses necessary to check the weight of the potatoes and writes the result to the standard output.
Input
The first (and the only one) line of the standard input contains three positive integers A, B and N, separated by single blanks and having the following meaning: the weights of masses and the declared weight of the potatoes in kilograms.
Output
Your program should print exactly one positive integer to the standard output – the minimum number of masses needed to check the weight of the potatoes.
If it is impossible to achieve using the given masses, you should
print NIE (the Polish for NO) instead.
Limits
1 ≤ A, B, N ≤ 109.
Example
| Input | Output | Explanation |
|
|
It is enough to put three masses of weight 14 to the right arm and two masses of weight 9 to the left arm. |
| Input | Output | Explanation |
|
|
It is enough to put five masses of weight 5 and two masses of weight 3 to the right arm. |
| Input | Output | Explanation |
|
|
It may be difficult to check the weight of the potatoes in this case… |