Панг считает, что нельзя приготовить омлет, не разбив яиц. Для подмножества $A \subseteq \{1, 2, \dots, n\}$ мы вычисляем значение $A$ следующим образом:

1. Инициализируем значение равным 0.
2. Для любого $i \in A$ прибавляем $a_i$ к значению.
3. Для любой пары целых чисел $(i, j)$, удовлетворяющих условиям $i \ge 2$, $j \ge 2$, $i \in A$ и $j \in A$, если существует целое число $k > 1$ такое, что $i^k = j$, вычитаем $b_j$ из значения.

Найдите максимально возможное значение среди всех вариантов выбора $A$.

Входные данные

Первая строка содержит единственное целое число $n$ ($1 \le n \le 100000$). Вторая строка содержит $n$ целых чисел $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 1000000000$). Третья строка содержит $n$ целых чисел $b_1, b_2, \dots, b_n$ ($1 \le b_i \le 1000000000$).

Выходные данные

Выведите единственное целое число $x$ — максимально возможное значение.

Примеры

Входные данные 1

4
1 1 1 2
1 1 1 1

Выходные данные 1

4

Входные данные 2

4
1 1 1 1
1 1 1 2

Выходные данные 2

3