Problem Description

Xiaoming goes to a banquet. There are $n$ dishes at the banquet, and each dish has a tastiness value. The tastiness of the $i$-th dish is $v_i$.

The banquet rules say that Xiaoming can select exactly two dishes, and the tastiness values of these two dishes must be coprime (i.e., their greatest common divisor is $1$).

Please help Xiaoming choose two dishes so that the sum of their tastiness values is as large as possible.

Input Format

The input has $2$ lines.

The first line contains a positive integer $n$, representing the number of dishes.

The second line contains $n$ integers $v_1, v_2, \cdots, v_n$, representing the tastiness values of the dishes. The integers are separated by spaces.

Output Format

Output one integer, representing the maximum possible sum of tastiness values of two coprime dishes.

5
3 5 7 35 105

38

Hint

Sample Explanation 1

The best choice is $3$ and $35$.

Note that the greatest common divisor of $105$ and any other dish is greater than $1$, so it cannot be part of a valid choice.

Constraints

$2 \le n \le 1000$, $1 \le v_i \le 1000000$.

The testdata guarantees that there are no dishes with the same tastiness value.

The testdata guarantees that there is at least one way to select two dishes.

Translated by ChatGPT 5