请注意,内存限制不正常。
给定一个整数 $$$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$$$,满足以下条件:对于 [1, i - 1]$$$ 中的每个 $$$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$$$)。
输出
打印一个整数 — 一组奇怪的最大成本。
示例
输入 #1
9 4 7 3 4 5 6 7 8 13 -2 3 -19 5 -6 7 -8 9 1
输出 #1
16
输入 #2
2 42 42 -37 13
输出 #2
0
输入 #3
2 42 42 13 -37
输出 #3
13
注意
第一个示例中成本最大的奇怪集合是 $$$\{1, 2, 4, 8, 9\}$$$。
第二个例子中成本最大的奇怪集合是空的。