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.

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.

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.