시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 256 MB222100.000%

문제

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$. 

입력

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)$.

출력

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

예제 입력 1

4
1 1 1 2
1 1 1 1

예제 출력 1

4

예제 입력 2

4
1 1 1 1
1 1 1 2

예제 출력 2

3