F. Funny Numbers
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Certain numbers are funny on their own, but next to other numbers, their funniness changes. In particular, the funniness $$$f(x_1, x_2)$$$ of a pair of numbers $$$x_1$$$ and $$$x_2$$$ is the number of common divisors between their respective funniness values $$$y_1$$$ and $$$y_2$$$. The funniness of a sequence is the sum of the funniness of every adjacent pair of numbers, or more formally:

$$$f(x_1, x_2, ..., x_n) = \sum_{i=1}^{n-1} f(x_i, x_{i+1})$$$

Note that this sequence must contain at least two elements, so the funniness of a single number $$$x_1$$$ is not defined.

Given $$$n$$$ distinct numbers and their funniness values, find the funniness of the funniest possible sequence that can be constructed.

Input

The first line of input contains $$$n$$$ ($$$2 \le n \le 18$$$), the number of funny numbers.

The second line contains $$$n$$$ integers, $$$x_1, x_2, ..., x_n$$$ ($$$1 \le x_i \le 10^9$$$), the distinct funny numbers.

The third line contains $$$n$$$ integers, $$$y_1, y_2, ..., y_n$$$ ($$$1 \le y_i \le 10^9$$$), the funniness value of each funny number.

Output

The output should be one line containing the maximum possible funniness of any sequence that consists of the given funny numbers.

Example
Input
4
41 42 67 69
12 20 24 16
Output
13
Note

One sequence with the maximum funniness is $$$42, 41, 67, 69$$$, which has a funniness of $$$f(42, 41) + f(41, 67) + f(67, 69) = 3 + 6 + 4 = 13$$$.