Remainder Game

Aoki is playing with a sequence of numbers a_{1}, a_{2}, ..., a_{N}. Every second, he performs the following operation :

• Choose a positive integer k. For each element of the sequence v, Aoki may choose to replace v with its remainder when divided by k, or do nothing with v. The cost of this operation is 2^{k} (regardless of how many elements he changes).

Aoki wants to turn the sequence into b_{1}, b_{2}, ..., b_{N} (the order of the elements is important). Determine if it is possible for Aoki to perform this task and if yes, find the minimum cost required.

Constraints

• 1 \leq N \leq 50
• 0 \leq a_{i}, b_{i} \leq 50
• All values in the input are integers.

Input

Input is given from Standard Input in the following format:

N a_{1} a_{2} ... a_{N} b_{1} b_{2} ... b_{N}

Output

Print the minimum cost required to turn the original sequence into b_{1}, b_{2}, ..., b_{N}. If the task is impossible, output -1 instead.

Examples

Input

3 19 10 14 0 3 4

Output

160

Input

3 19 15 14 0 0 0

Output

2

Input

2 8 13 5 13

Output

-1

Input

4 2 0 1 8 2 0 1 8

Output

0

Input

1 50 13

Output

137438953472

inputFormat

input are integers.

Input

Input is given from Standard Input in the following format:

N a_{1} a_{2} ... a_{N} b_{1} b_{2} ... b_{N}

outputFormat

Output

Print the minimum cost required to turn the original sequence into b_{1}, b_{2}, ..., b_{N}. If the task is impossible, output -1 instead.

Examples

Input

3 19 10 14 0 3 4

Output

160

Input

3 19 15 14 0 0 0

Output

2

Input

2 8 13 5 13

Output

-1

Input

4 2 0 1 8 2 0 1 8

Output

0

Input

1 50 13

Output

137438953472

样例

1
50
13

137438953472