Canadian Informatics Workshop 2026: Day 2, Problem 1

Morgan found a mysterious gumball machine under an old tarp in their attic. The machine has two buttons—one on the left and one on the right—and two counters labelled ~A~ and ~B~. Both counters start at zero. If Morgan presses the left button, counter ~A~ increases by one, and the machine dispenses ~B~ gumballs. If Morgan presses the right button, counter ~B~ increases by one, and the machine dispenses ~A~ gumballs. The machine may look small, but it contains a seemingly infinite number of gumballs and will never run out.

Using the fewest button presses, Morgan wants to get exactly ~N~ gumballs from the machine in total. Can you help them achieve this?

Input Specification

The first and only line of input contains a single integer, ~N~ (~0 \le N \le 10^9~), the number of gumballs Morgan wants to get from the machine.

The following table shows how the available 25 marks are distributed:

Marks Awarded	Bounds on ~N~	Additional Constraints
7 marks	~0\leq N\leq 200~	None
5 marks	~0\leq N\leq 2\,000~	None
3 marks	~0 \le N \le 10^9~	The minimum number of button presses can always be achieved by alternating between left and right presses
10 marks	~0 \leq N \le 10^9~	None

Output Specification

Output a single integer: the minimum number of button presses Morgan must perform to dispense exactly ~N~ gumballs from the machine, or ~-1~ if it is impossible to do so.

Sample Input

6

Sample Output

5

Explanation for Sample Output

Morgan presses the left button twice, setting ~A~ to 2 and dispensing no gumballs. Then they press the right button twice, setting ~B~ to 2 and dispensing 4 gumballs (2 on each press). Finally, they press the left button once, setting ~A~ to 3 and dispensing 2 more gumballs for a total of 6. It is impossible to dispense exactly 6 gumballs in fewer than 5 presses.