Value

Pang은 달걀을 깨지 않고서는 오믈렛을 만들 수 없다고 믿는다.

집합 $\{1,2,\ldots,n\}$의 부분집합 $A$에 대해 점수를 다음과 같이 계산한다.

1. 점수를 $0$으로 초기화한다.
2. $i\in A$인 모든 $i$에 대해 점수에 $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$를 적절히 고를 때 얻을 수 있는 최대 점수를 구하라.

첫째 줄에 정수 $n$이 주어진다. $(1\le n\le 100000)$

둘째 줄에 $n$개의 정수 $a_1,a_2,\ldots,a_n$이 주어진다. $(1\le a_i\le 1000000000)$

셋째 줄에 $n$개의 정수 $b_1,b_2,\ldots,b_n$이 주어진다. $(1\le b_i\le 1000000000)$

얻을 수 있는 최대 점수 $x$를 한 줄에 출력한다.