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.

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.

Strange Set

Examples