406658: GYM102471 M Value

M. Valuetime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Pang believes that one cannot make an omelet without breaking eggs.

For a subset $$$A$$$ of $$$\{1,2,\ldots,n\}$$$, we calculate the score of $$$A$$$ as follows:

1. Initialize the score as $$$0$$$.
2. For any $$$i\in A$$$, add $$$a_i$$$ to the score.
3. For any pair of integers $$$(i, j)$$$ satisfying $$$i\ge 2$$$, $$$j\ge 2$$$, $$$i\in A$$$ and $$$j\in A$$$, if there exists positive integer $$$k > 1$$$ such that $$$i^k=j$$$, subtract $$$b_j$$$ from the score.

Find the maximum possible score over the choice of $$$A$$$. Input

The first line contains a single integer $$$n$$$ $$$(1\le n\le 100000)$$$.

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ $$$(1\le a_i\le 1000000000)$$$.

The third line contains $$$n$$$ integers $$$b_1,b_2,\ldots,b_n$$$ $$$(1\le b_i\le 1000000000)$$$.

Output

Print a single integer $$$x$$$ — the maximum possible score.

ExamplesInput

4
1 1 1 2
1 1 1 1

Output

4

Input

4
1 1 1 1
1 1 1 2

Output

3