F. Странное множество
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
32 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Обратите внимание на необычное ограничение по памяти.

Задано целое число $$$n$$$ и две последовательности $$$a_1, a_2, \dots, a_n$$$ и $$$b_1, b_2, \dots, b_n$$$.

Назовем множество целых чисел $$$S$$$ такое, что $$$S \subseteq \{1, 2, 3, \dots, n\}$$$ странным, если для каждого элемента $$$i$$$ из $$$S$$$ выполняется следующее условие: для каждого $$$j \in [1, i - 1]$$$, если $$$a_j$$$ делит $$$a_i$$$, то $$$j$$$ также входит в $$$S$$$. Пустое множество является странным.

Стоимостью множества $$$S$$$ назовем величину $$$\sum\limits_{i \in S} b_i$$$. Вам необходимо найти максимальную возможную стоимость странного множества.

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

Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 3000$$$).

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 100$$$).

Третья строка содержит $$$n$$$ целых чисел $$$b_1, b_2, \dots, b_n$$$ ($$$-10^5 \le b_i \le 10^5$$$).

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

Выведите одно целое число — максимальную стоимость странного множества.

Примеры
Входные данные
9
4 7 3 4 5 6 7 8 13
-2 3 -19 5 -6 7 -8 9 1
Выходные данные
16
Входные данные
2
42 42
-37 13
Выходные данные
0
Входные данные
2
42 42
13 -37
Выходные данные
13
Примечание

Для первого примера странное множество с максимальной стоимостью выглядит следующим образом — $$$\{1, 2, 4, 8, 9\}$$$.

Для второго примера странным множеством с максимальной стоимостью является пустое множество.