Обратите внимание на необычное ограничение по памяти.
Задано целое число $$$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\}$$$.
Для второго примера странным множеством с максимальной стоимостью является пустое множество.
Название |
---|