C - Remainder Game

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 700

問題文

アオキは数列 a_{1}, a_{2}, ..., a_{N} で遊んでいます。1 秒ごとに、アオキは次の操作を行います。

  • 正の整数 k を選ぶ。数列のそれぞれの要素 v について、アオキは v を「vk で割った余り」に置き換えるか、v をそのままにするかを選べる。この一連の操作のコストは(書き換えた要素の数によらず)2^{k} である。

アオキは、数列を b_{1}, b_{2}, ..., b_{N} に変えたいです(要素の順番も考慮します)。この目的を達成することが可能か判定し、可能である場合は必要な最小のコストを求めてください。

制約

  • 1 \leq N \leq 50
  • 0 \leq a_{i}, b_{i} \leq 50
  • 入力中の値はすべて整数である。

入力

入力は標準入力から以下の形式で与えられる。

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

出力

はじめの数列を b_{1}, b_{2}, ..., b_{N} に変えるのに必要な最小のコストを出力せよ。目的の達成が不可能である場合は、代わりに -1 と出力せよ。


入力例 1

3
19 10 14
0 3 4

出力例 1

160

操作手順の例を挙げます。

  • k = 7 を選ぶ。195 に、103 に置き換えて 14 はそのままにする。数列は 5, 3, 14 となる。
  • k = 5 を選ぶ。50 に置き換え、3 はそのままにして 144 に置き換える。数列は 0, 3, 4 となる。

合計コストは 2^{7} + 2^{5} = 160 です。


入力例 2

3
19 15 14
0 0 0

出力例 2

2

k = 1 を選び、すべてを 0 に変えるとよいです。コストは 2^{1} = 2 です。


入力例 3

2
8 13
5 13

出力例 3

-1

与えられた操作では 85 に変えることができないため、目的の達成は不可能です。


入力例 4

4
2 0 1 8
2 0 1 8

出力例 4

0

この場合は何もする必要がありません。コストは 0 です。


入力例 5

1
50
13

出力例 5

137438953472

オーバーフローにご注意。

Score : 700 points

Problem Statement

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.


Sample Input 1

3
19 10 14
0 3 4

Sample Output 1

160

Here's a possible sequence of operations :

  • Choose k = 7. Replace 19 with 5, 10 with 3 and do nothing to 14. The sequence is now 5, 3, 14.

  • Choose k = 5. Replace 5 with 0, do nothing to 3 and replace 14 with 4. The sequence is now 0, 3, 4.

The total cost is 2^{7} + 2^{5} = 160.


Sample Input 2

3
19 15 14
0 0 0

Sample Output 2

2

Aoki can just choose k = 1 and turn everything into 0. The cost is 2^{1} = 2.


Sample Input 3

2
8 13
5 13

Sample Output 3

-1

The task is impossible because we can never turn 8 into 5 using the given operation.


Sample Input 4

4
2 0 1 8
2 0 1 8

Sample Output 4

0

Aoki doesn't need to do anything here. The cost is 0.


Sample Input 5

1
50
13

Sample Output 5

137438953472

Beware of overflow issues.