B. Maximize
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given two arrays $$$a$$$ and $$$b$$$ with the length of $$$n$$$ filled with numbers.

Let us consider that the result of formula $$$\sum_{i = 1}^n GCD(a_i, b_i)$$$ is their coolness

You can shuffle numbers in a given array $$$b$$$ as you like. You should find maximum coolness.

Input

In the first row there is one positive integer value$$$n$$$ ($$$1 \leq n \leq 700$$$) — length of both arrays.

The second row consists of numbers $$$a_1, a_2, ... , a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — elements of the first array.

The third row consists of numbers $$$b_1, b_2, ... , b_n$$$ ($$$1 \leq b_i \leq 10^9$$$) — elements of the second array.

Output

You should print the maximum coolness.

Examples
Input
3
1 2 3
5 3 6
Output
6
Input
4
6 4 6 5
1 5 3 2
Output
11