P17011 [GESP202606 Level 5] Banquet.

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.

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 one integer, representing the maximum possible sum of tastiness values of two coprime dishes.

### 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