P5154 数列游戏

本题改编自真实事件，特别鸣谢倪星宇同学提供创意支持。 有一次，HKE 和 LJC 在玩一个有趣的数列游戏。

游戏规则如下： LJC 写下两个长度均为 $N$ 的正整数数列 $A$ 和 $B$。两个数列一一对应，即对于每个 $i$ 都有一对 $(A_i, B_i)$。 HKE 每次可以选择一对 **相邻的**数 $A[i]$ 和 $A[i+1]$，**如果它们不互质（即 $\gcd(A[i], A[i+1]) > 1$**，他可以将这一对消除，并获得 $B[i] + B[i+1]$ 分数。 被消除的一对数从两个数列中同时移除，并使两个数列重新紧密排列（即剩余元素自动左移）。 当数列中**所有相邻的数对都互质时**，游戏结束。HKE 想知道他最多可以获得多少分数。

* 第 1 行：一个整数 $N$（表示数列的长度） * 第 2 行：$N$ 个整数，表示数列 $A_1, A_2, \ldots, A_N$ * 第 3 行：$N$ 个整数，表示数列 $B_1, B_2, \ldots, B_N$

* 输出一个整数，表示 HKE 可以获得的最大总得分。

### 样例解释 一种最优的策略如下： * 第一次消去 $A[2]=8$ 和 $A[3]=6$，获得 $B[2]+B[3]=19+12=31$ 分； * 更新数列后为：$9, 5, 6, 3$，$11, 17, 18, 15$； * 第二次消去 $A[3]=6$ 和 $A[4]=3$，获得 $B[3]+B[4]=18+15=33$ 分； * 总得分为 $31+33=64$。 ### 数据范围与限制 * 对于 30% 的数据，$N \leq 20$； * 对于 60% 的数据，$N \leq 100$； * 对于 80% 的数据，$N \leq 500$； * 对于 100% 的数据，$N \leq 800$； * 保证 $1 \leq A_i, B_i \leq 10^9$。