CF1473F.Strange Set

Note that the memory limit is unusual.

You are given an integer $n$ and two sequences $a_1, a_2, \dots, a_n$ and $b_1, b_2, \dots, b_n$.

Let's call a set of integers $S$ such that $S \subseteq {1, 2, 3, \dots, n}$ strange, if, for every element $i$ of $S$, the following condition is met: for every $j \in [1, i - 1]$, if $a_j$ divides $a_i$, then $j$ is also included in $S$. An empty set is always strange.

The cost of the set $S$ is $\sum\limits_{i \in S} b_i$. You have to calculate the maximum possible cost of a strange set.

注意：内存限制较为特殊。

给你一个整数 $n$ 和两个序列 $a_1, a_2, \dots, a_n$ 与 $b_1, b_2, \dots, b_n$。

我们称一个整数集合 $S$（满足 $S \subseteq \{1, 2, 3, \dots, n\}$）为“奇异的”，当且仅当对 $S$ 中的每个元素 $i$，均满足如下条件：对每个 $j \in [1, i - 1]$，若 $a_j$ 整除 $a_i$，则 $j$ 也必须属于 $S$。空集总是奇异的。

集合 $S$ 的代价定义为 $\sum\limits_{i \in S} b_i$。你需要计算奇异集合的最大可能代价。

The first line contains one integer $n$ ($1 \le n \le 3000$).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 100$).

The third line contains $n$ integers $b_1, b_2, \dots, b_n$ ($-10^5 \le b_i \le 10^5$).

第一行包含一个整数 $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$）。

Print one integer — the maximum cost of a strange set.

输出一个整数——奇异集合的最大代价。

The strange set with the maximum cost in the first example is ${1, 2, 4, 8, 9}$.

The strange set with the maximum cost in the second example is empty.

第一个样例中，成本最大的“奇怪集合”为 $\{1, 2, 4, 8, 9\}$。

第二个样例中，成本最大的“奇怪集合”为空集。