Strange Set

题意翻译

**请注意本题的时间与空间限制** 你有两个长度均为 $n$ 的序列 $a_1,a_2,\dots,a_n$ 和 $b_1,b_2,\dots,b_n$。 我们定义一个集合 $S\subseteq\{1,2,\dots,n\}$ 是奇怪的，当且仅当：对于任意 $i\in S$，如果有 $j\in [1,i-1]$，满足 $a_j|a_i$，则也有 $j\in S$。特别地，**空集**总是一个奇怪的集合。 定义一个集合 $S$ 的权为 $\sum_{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,2,4,8,9\}$。 第二个样例中，权值最大的奇怪集合为 $\varnothing$。

题目描述

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.

输入输出格式

输入格式

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 $ ).

输出格式

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

输入输出样例

输入样例 #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

说明

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.