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.
9 4 7 3 4 5 6 7 8 13 -2 3 -19 5 -6 7 -8 9 1
16
2 42 42 -37 13
0
2 42 42 13 -37
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.
Name |
---|