背景

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

描述

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

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

②.a_ia_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,0001\leqslant a_i,b_i \leqslant 10^6

样例解释

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

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