数列游戏

题目背景

此题为改编题,特别鸣谢倪星宇同学。 有一次,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 列被删去的可能最大和。

输入输出样例

输入样例 #1

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

输出样例 #1

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。