题目描述

アオキ正在玩一个数列 $a_{1},\ a_{2},\ ...,\ a_{N}$。每过 $1$ 秒，アオキ会进行如下操作：

• 选择一个正整数 $k$。对于数列中的每个元素 $v$，アオキ可以选择将 $v$ 替换为“$v$ 除以 $k$ 的余数”，或者保持 $v$ 不变。无论修改了多少个元素，这一系列操作的代价都是 $2^{k}$。

アオキ想要把数列变成 $b_{1},\ b_{2},\ ...,\ b_{N}$（元素的顺序也要一致）。请判断能否实现这个目标，如果可以，请求出所需的最小代价。

输入格式

输入从标准输入读取，格式如下：

$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

输出

160

样例 2

输入

3
19 15 14
0 0 0

输出

2

样例 3

输入

2
8 13
5 13

输出

-1

样例 4

输入

4
2 0 1 8
2 0 1 8

输出

0

样例 5

输入

1
50
13

输出

137438953472

说明/提示

限制条件

• $1\leq N\leq 50$
• $0\leq a_{i},\ b_{i}\leq 50$
• 输入中的所有值均为整数。

样例解释 1

以下是操作步骤的一个例子：

• 选择 $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

选择 $k=1$，将所有元素都变为 $0$ 即可。总代价为 $2^{1}=2$。

样例解释 3

由于无法通过给定的操作将 $8$ 变为 $5$，因此无法实现目标。

样例解释 4

此时无需进行任何操作，总代价为 $0$。

样例解释 5

请注意防止溢出。

由 ChatGPT 4.1 翻译