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 square pieces of wood. The -th piece of wood has integer length and width of units.
A piece of wood with length and width is divided into sections that consist of rows with columns each. Initially, there is a nail placed on the bottom right corner of each wood board.
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 and be minimal among all possible lengths.
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?
Subtask 1 [20%]
Subtask 2 [20%]
Subtask 3 [30%]
Subtask 4 [30%]
No additional constraints.
The first line contains two integers and .
The next line contains .
On a single line, print the minimum square board size with side lengths less than or equal to to be added such that Mike will win if both players play optimally. If no solution exists, output on a single line instead.
Sample Input 1
2 4 6 2
Sample Output 1
Explanation for Sample Output 1
After adding a square wood board with side length , it can be shown that Mike will win the game if both players play optimally. A sample interaction where each player plays optimally is shown below.
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 is the minimal solution.
Sample Input 2
1 68 1
Sample Output 2
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 , which is the minimal possible board size.
Sample Input 3
4 10 9 7 3 8
Sample Output 3
Explanation for Sample Output 3
It can be shown that no square board with side lengths up to once added will allow Mike to win if both players play optimally.
Sample Input 4
6 29 4 1 4 20 6 9
Sample Output 4