Pangは、卵を割らずにオムレツを作ることはできないと信じている。 $\{1, 2, \dots, n\}$ の部分集合 $A$ に対して、そのスコアを以下のように計算する。

1. スコアを $0$ に初期化する。
2. すべての $i \in A$ について、$a_i$ をスコアに加算する。
3. $i \ge 2, j \ge 2, i \in A, j \in A$ を満たすすべての整数の組 $(i, j)$ について、もし $i^k = j$ を満たす整数 $k > 1$ が存在する場合、スコアから $b_j$ を減算する。

$A$ の選択における最大スコアを求めよ。

入力

1行目に整数 $n$ ($1 \le n \le 100000$) が与えられる。 2行目に $n$ 個の整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 1000000000$) が与えられる。 3行目に $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