The Alchemist Skr

View as PDF

Submit solution


Points: 1
Time limit: 1.0s
Memory limit: 256M

Problem types

Influenced a little too heavily by the popular Coelho book The Alchemist, Skr quit studying algorithms and started studying chemistry at home. Having conducted numerous experiments in his makeshift lab, he finally completed his hand sanitizer prototype, with the hopes of making the most of the COVID pandemic. Next step in Skr’s venture is getting rid of all the extra chemical components he bought while he was working on the prototype.

In Skr’s storage, there are 3 types of chemical components named \(\mathbf{A}\), \(\mathbf{B}\) and \(\mathbf{C}\). When a liter of two different types of components enter into a reaction, all the input to that reaction disappears and a liter of the third type is produced. For instance, if a liter of \(\mathbf{A}\) and a liter of \(\mathbf{B}\) enter into a chemical reaction, all the input (2 liters in total) is consumed and a liter of \(\mathbf{C}\) is produced. Similarly, a liter of \(\mathbf{A}\) and a liter of \(\mathbf{C}\) produce a liter of \(\mathbf{B}\), while a liter of \(\mathbf{B}\) and a liter of \(\mathbf{C}\) produce a liter of \(\mathbf{A}\).

With his prototype ready to be presented to investors, Skr is now planning to become a successful hand sanitizer salesman, and he has no further use for the experimental chemicals in his storage. He wants to sell those chemicals to a waste management company, but it is too expensive for Skr to send those chemicals separately. That’s why, he needs to reduce the 3 types of chemicals in his storage into 1, as soon as possible.

As he hasn’t studied algorithms in years, Skr doesn’t know how he can calculate the minimum number of reactions in which he can reduce those 3 types of chemical components into a single type. He now asks you, an acquaintance of his from his competitive programming days, for help.

  • Skr’s lab equipment prevents any reactions with non-integer amounts of input. So, two chemicals can enter a reaction only in equal and integer quantities.
  • In a chemical reaction, each pair of liters of inputs is considered to be a separate reaction. Hence, if 2 liters (each) of chemicals \(\mathbf{A}\) and \(\mathbf{B}\) enter into a reaction and produce 2 liters of \(\mathbf{C}\), this should be considered as 2 separate reactions.
  • Last remaining chemical component can be of any type.

Input

The input contains 3 integers \(\mathbf{A}\), \(\mathbf{B}\) ve \(\mathbf{C}\), which represent the initial amount (in liters) of components \(\mathbf{A}\), \(\mathbf{B}\) and \(\mathbf{C}\) that Skr has in his storage.

  • \(0 \leq \mathbf{A, B, C} \leq 2^{31}\)

It is guaranteed that the input will not be 0 0 0.

Output

The output consists of a single integer \(\mathbf{N}\), representing the minimum number of reactions required to reduce the number of types of chemicals in Skr’s storage to 1.

Print -1 if it is impossible to reduce the remaining type of chemicals to 1.

Example

Input 1:

1 1 1

Output 1:

1

Input 2:

3 1 0

Output 2:

3

Explanation

In the first input, if a liter of any two chemical components undergo a single chemical reaction, we end up with a total of 2 liters of the third type. Since there are no chemicals of any other type are left, in this case, it takes 1 reaction to reduce the initial amount of chemicals into a single type.