Pang 认为不打破鸡蛋就做不成煎蛋卷。 对于 $\{1, 2, \dots, n\}$ 的一个子集 $A$，我们按如下方式计算 $A$ 的得分：

1. 初始化得分为 $0$。
2. 对于任何 $i \in A$，将 $a_i$ 加入得分。
3. 对于任何满足 $i \ge 2, j \ge 2, i \in A$ 且 $j \in A$ 的整数对 $(i, j)$，如果存在正整数 $k > 1$ 使得 $i^k = j$，则从得分中减去 $b_j$。

求在所有可能的 $A$ 的选择中，得分的最大值。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 100000$)。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 1000000000$)。 第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$ ($1 \le b_i \le 1000000000$)。

输出格式

输出一个整数 $x$ —— 最大可能的得分。

样例

样例输入 1

4
1 1 1 2
1 1 1 1

样例输出 1

4

样例输入 2

4
1 1 1 1
1 1 1 2

样例输出 2

3