Pang uważa, że nie da się zrobić omletu bez rozbijania jajek. Dla podzbioru $A$ zbioru $\{1, 2, \dots, n\}$ obliczamy wynik $A$ w następujący sposób:

1. Inicjalizujemy wynik jako 0.
2. Dla każdego $i \in A$ dodajemy $a_i$ do wyniku.
3. Dla każdej pary liczb całkowitych $(i, j)$ spełniających $i \ge 2$, $j \ge 2$, $i \in A$ oraz $j \in A$, jeśli istnieje liczba całkowita dodatnia $k > 1$ taka, że $i^k = j$, odejmujemy $b_j$ od wyniku.

Znajdź maksymalny możliwy wynik przy optymalnym wyborze zbioru $A$.

Wejście

Pierwsza linia zawiera pojedynczą liczbę całkowitą $n$ ($1 \le n \le 100000$). Druga linia zawiera $n$ liczb całkowitych $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 1000000000$). Trzecia linia zawiera $n$ liczb całkowitych $b_1, b_2, \dots, b_n$ ($1 \le b_i \le 1000000000$).

Wyjście

Wypisz pojedynczą liczbę całkowitą $x$ — maksymalny możliwy wynik.

Przykład

Wejście 1

4
1 1 1 2
1 1 1 1

Wyjście 1

4

Wejście 2

4
1 1 1 1
1 1 1 2

Wyjście 2

3