题目描述

Aoki正在玩一个数字序列 $a_{1}, a_{2}, ..., a_{N}$。每秒钟，他执行以下操作：

• 选择一个正整数 $k$。对于序列中的每个元素 $v$，Aoki 可以选择用 $k$ 整除 $v$ 后的余数替换 $v$，或者保持不变。这个操作的代价是 $2^{k}$（无论他改变了多少个元素）。

Aoki想要将序列转换为 $b_{1}, b_{2}, ..., b_{N}$（元素的顺序很重要）。判断是否可能让 Aoki 执行这个任务，如果可以，找到所需的最小代价。

约束条件

• $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$。将 $19$ 替换为 $5$，$10$ 替换为 $3$，不修改 $14$。序列现在为 $5, 3, 14$。

• 选择 $k = 5$。将 $5$ 替换为 $0$，保持不变的是 $3$，将 $14$ 替换为 $4$。序列现在为 $0, 3, 4$。

总代价为 $2^{7} + 2^{5} = 160$。

示例输入 2

3
19 15 14
0 0 0

示例输出 2

2

Aoki可以选择 $k = 1$，把所有元素变成 $0$。代价是 $2^{1} = 2$。

示例输入 3

2
8 13
5 13

示例输出 3

-1

任务无法完成，因为使用给定的操作无法将 $8$ 转换为 $5$。

示例输入 4

4
2 0 1 8
2 0 1 8

示例输出 4

0

这里不需要任何操作。代价为 $0$。

示例输入 5

1
50
13

示例输出 5

137438953472

注意溢出问题。