Description

$\textit{Pang}$ 认为“要做蛋卷，必先打破鸡蛋”。

对于集合 $\{1,2,\ldots,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$ 的最大可能得分。

Input Format

第一行包含一个整数 $n$，表示元素个数 $(1\le n\le 100000)$。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示每个元素的加分值 $(1\le a_i\le 1000000000)$。

第三行包含 $n$ 个整数 $b_1,b_2,\ldots,b_n$，表示每个元素的扣分值 $(1\le b_i\le 1000000000)$。

Output Format

输出一个整数 $x$，表示最大可能得分。

4
1 1 1 2
1 1 1 1

4

4
1 1 1 1
1 1 1 2

3

Hint

由 ChatGPT 4.1 翻译