题目背景

此题为改编题，特别鸣谢倪星宇同学。

有一次，HKE和LJC在玩一个游戏。

题目描述

游戏的规则是这样的：LJC在纸上写下两个长度均为N的数列A和B，两个数列一一对应。HKE每次可以找两个相邻的数A[i]和A[i+1]，如果它们两个不互质，HKE可以选择得到(B[i]+B[i+1])分，然后擦掉A和B位置上的第i,i+1个数，并把两个序列重新按顺序编号。当所有相邻的数互质时，游戏结束。

HKE想知道他最大得分是多少。

输入格式

第1 行一个整数N；

第2 行N 个整数，依次表示Ai；

第3 行N 个整数，依次表示Bi。

输出格式

仅含一个整数，表示B 列被删去的可能最大和。

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

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

提示

对于30%的数据，N ≤ 20；

对于60%的数据，N ≤ 100；

对于80%的数据，N ≤ 500

对于100%的数据，N ≤ 800, 1 ≤ Ai, Bi ≤ 10^9。