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

4

範例 2

4
1 1 1 1
1 1 1 2

3