题目背景

本题改编自真实事件，特别鸣谢倪星宇同学提供创意支持。

有一次，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 可以获得的最大总得分。

6
9 8 6 5 6 3
11 19 12 17 18 15

64
//解释：擦去A[2],A[3]与A[5],A[6]，得分为64

提示

样例解释

一种最优的策略如下：

• 第一次消去 $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$。