千钧一发 Katharon ＃1

背景

在你正确计算表达式的值以后，石板又出现了新的状况，然而这次情况十分紧急，如果无法做出正确的选择，Katherine皇后很可能再也无法和Kanari国王在一起了。

描述

石板上突然出现n个奇怪的装置，Kanari国王仔细观察，发现每个装置上面都写有两个正整数，我们记第i的装置上的两个正整数分别为a_i和b_i。其中a_i表示这个装置的特征值，b_i表示这个装置蕴含的能量值。现在请你在这n个装置中选择一部分出来，使得选择的任意两个装置i和j（i\neq j）至少满足下面两个条件之一：

①.不存在正整数T使得a_i^2+a_j^2=T^2。

②.a_i和a_j有大于1的公因子。

你的目标就是使得选出来装置的能量值总和最大，如果你回答正确，说不定石板会按照它所说的，将Katharon国最珍贵的财产交出来，否则国王、皇后以及你的小命都将难保。

输入格式

第一行一个正整数n。

第二行共包括n个正整数，第i个正整数表示a_i。

第三行共包括n个正整数，第i个正整数表示b_i。

输出格式

共一行，包括一个正整数，表示在合法的选择条件下，可以获得的能量值总和的最大值。

样例输入

4
3 4 5 12
9 8 30 9

样例输出

39

数据范围与约定

对于全部数据满足1\leqslant n\leqslant 1,000，1\leqslant a_i,b_i \leqslant 10^6。

样例解释

选择第一个和第三个装置，由于不存在正整数T，使得3^2+5^2=T^2，因此是合法的。

所获得的能量值为9+30=39。