题目背景

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

题目描述

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

1. 不存在正整数 $T$ 使得 $a_i^2+a_j^2=T^2$
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\le n \le 10^3,1\le a_i,b_i\le 10^6$

题目来源

Katharon+#1