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.