Mike is tired of working with nails and wood in the Canadian Carpentry Challenge (CCC). So, he decided to take a break and invited Nils to come play a game with him. To play this game, Mike has gathered
A piece of wood with length
Mike and Nils will take turns during the game. On each player's turn, they will choose exactly one of the wood boards, and then choose one of the following moves:
- Make a horizontal cut across the entire wood board such that the length and width of both pieces are integral after the cut, and discard the piece that does not contain the nail.
- Make a vertical cut across the entire wood board such that the length and width of both pieces are integral after the cut, and discard the piece that does not contain the nail.
- Move the nail
units left such that is a positive integer and the nail remains on the board. - Move the nail
units up such that is a positive integer and the nail remains on the board. - Move the nail
units left and units up such that is a positive integer and the nail remains on the board.
When a player is unable to make a move, they lose, and the other player wins. Nils will go first.
Mike wants to win the game, and he will make sure he does by adding exactly one more square wood board of integral side length to the game. Like any other piece of wood, the added board will have a nail on the bottom right corner. Since Mike does not want to arouse suspicion, the additional square board's side length must not exceed
Can you tell Mike the smallest board to add so that he will win if both Nils and him play optimally, or report that it is impossible to do so?
Constraints
Subtask 1 [20%]
Subtask 2 [20%]
Subtask 3 [30%]
Subtask 4 [30%]
No additional constraints.
Input Specification
The first line contains two integers
The next line contains
Output Specification
On a single line, print the minimum square board size with side lengths less than or equal to
Sample Input 1
2 4
6 2
Sample Output 1
3
Explanation for Sample Output 1
After adding a square wood board with side length
At the end of the game, Nils is unable to make a valid move, so Mike wins. It can be shown that adding a square board of side length
Sample Input 2
1 68
1
Sample Output 2
1
Explanation for Sample Output 2
Even though Mike will already win as Nils is unable to make any move at the start, he must add another wood board to the game. So, he can add a square board with side lengths of
Sample Input 3
4 10
9 7 3 8
Sample Output 3
-1
Explanation for Sample Output 3
It can be shown that no square board with side lengths up to
Sample Input 4
6 29
4 1 4 20 6 9
Sample Output 4
21
Comments