Description

有\(1-n\)的整数各一个，你可以从中选择若干个，你的收益如下：
如果你选中了\(i\)，那么可以得到\(a_i\)元。
如果你同时选中了\(i(i>=2)\)和\(j(j>=2)\)，并且存在整数\(k(k>1)\)，使得\(i^k=j\)，那么会损失\(b_j\)元。
求最大收益。

Format

Input

每个测试点仅包含一组数据。
第一行一个整数\(n(1<=n<=100000)\)。
接下来一行\(n\)个整数，第\(i\)个整数表示\(a_i(1<=a_i<=10^9)\)。
接下来一行\(n\)个整数，第\(i\)个整数表示\(b_i(1<=b_i<=10^9)\)。

Output

输出一行一个整数，表示最大收益。

Sample 1

Input

4
1 1 1 2
1 1 1 1

Output

4

Sample 2

Input

4
1 1 1 1
1 1 1 2

Output

3

Limitation

1s, 1GB for each test case.

Source

Vijos Original