Strange Set

Note that the memory limit is unusual.

You are given an integer n and two sequences a_1, a_2, ..., a_n and b_1, b_2, ..., b_n.

Let's call a set of integers S such that S ⊆ {1, 2, 3, ..., n} strange, if, for every element i of S, the following condition is met: for every j ∈ [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 ∑_{i ∈ S} b_i. You have to calculate the maximum possible cost of a strange set.

Input

The first line contains one integer n (1 ≤ n ≤ 3000).

The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 100).

The third line contains n integers b_1, b_2, ..., b_n (-10^5 ≤ b_i ≤ 10^5).

Output

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

Examples

Input

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

Output

16

Input

2 42 42 -37 13

Output

0

Input

2 42 42 13 -37

Output

13

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.

inputFormat

Input

The first line contains one integer n (1 ≤ n ≤ 3000).

The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 100).

The third line contains n integers b_1, b_2, ..., b_n (-10^5 ≤ b_i ≤ 10^5).

outputFormat

Output

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

Examples

Input

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

Output

16

Input

2 42 42 -37 13

Output

0

Input

2 42 42 13 -37

Output

13

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.

样例

2
42 42
-37 13

0

</p>