Pang 认为不打破鸡蛋就做不成煎蛋卷。 对于 $\{1, 2, \dots, n\}$ 的一个子集 $A$，我们按如下方式计算 $A$ 的得分：
- 初始化得分为 $0$。
- 对于任何 $i \in A$，将 $a_i$ 加入得分。
- 对于任何满足 $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