Strange Set

4000ms

32768K

Description:

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.

Input:

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

Output:

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

Sample Input:

9
4 7 3 4 5 6 7 8 13
-2 3 -19 5 -6 7 -8 9 1

Sample Output:

Sample Input:

2
42 42
-37 13

Sample Output:

Sample Input:

2
42 42
13 -37

Sample Output:

Note:

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.

Informação

Provedor Codeforces

Código CF1473F