← 返回题目列表

Codeforces · 1473/F

F. 奇怪的设定

中文机器翻译题面 查看原题

请注意,内存限制不正常。

给定一个整数 $$$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\}$$$。

第二个例子中成本最大的奇怪集合是空的。