题目描述

混沌散去，序列王国迎来了秩序的黎明。

王国的贤者们以“数能”为基，铸造出一座名为「方阵」的能量矩阵。

这座矩阵是王国的心脏——它由 $2\times n$ 个能量单元构成，第 $i$ 行第 $j$ 列的能量为 $a_{i,j}$。

然而，为了维持方阵的稳定，贤者们签订了「方阵的契约」——必须将整个矩阵划分成若干个四连通的能量块。对于一个能量块，其强度定义为该块中所有能量值的最小公倍数（LCM）。

整个方阵的紊乱程度则等于所有能量块强度之和。贤者们请求你帮忙计算出最小的方阵紊乱程度。

输入格式

第一行包含一个整数 $n$，表示矩阵的大小。

第二行包含 $n$ 个整数，其中第 $i$ 个整数表示 $a_{1,i}$。

第三行包含 $n$ 个整数，其中第 $i$ 个整数表示 $a_{2,i}$。

输出格式

输出一行一个整数，表示方阵紊乱程度的最小值。

输入输出样例 #1

输入 #1

6
5 1 9 4 1 14
3 1 10 8 7 9

输出 #1

53

输入输出样例 #2

输入 #2

7
4 8 4 4 4 7 14
12 6 4 4 7 4 2

输出 #2

45

说明 / 提示

数据范围

对于所有数据，保证：

• $1\le n\le 1000$；
• $1\le a_{i,j}$，且 $\sum a_{i,j}\le 10^{18}$。

特殊性质 A：$a_{i,j}$ 为 $2$ 的幂。

特殊性质 B：保证存在一种最优划分方案，使得每个连通块的强度均不超过 $5000$。

样例解释 #1

具体划分如下图：

所有连通块的 LCM 之和为：$3+10+9+8+14+9=53$。

样例解释 #2

具体划分如下图：

所有连通块的 LCM 之和为：$8+12+7+4+14=45$。