Problem Description

Little A has a sequence of length $n$, denoted as $a_1, a_2, \cdots, a_n$.

He wants to select some numbers from this sequence, denoted as $b_1, b_2, \cdots, b_k$, such that for every $i$ (where $1 \leq i \leq k$), $b_i$ is either the maximum value in sequence $b$ or there exists a position $j$ where $b_j > b_i$ and $b_i + b_j + \gcd(b_i, b_j) = \mathrm{lcm}(b_i, b_j)$.

• If you are not familiar with $\gcd$ and $\mathrm{lcm}$, you can refer to the links in the "Help/Hints" section at the bottom.

Little A wants to maximize the sum of the selected numbers. Please find this maximum sum.

Input Format

The first line contains an integer $n$, representing the length of the sequence.

The second line contains $n$ integers $a_1, a_2, \cdots, a_n$.

Output Format

Output a single integer, which is the answer.

Sample Input and Output

Sample Input #1

4
4 3 2 1

Sample Output #1

5

Sample Input #2

10
6 7 18 4 17 10 9 1 3 8

Sample Output #2

19

Sample Input #3

3
123456789 234567890 123456789

Sample Output #3

246913578

Notes

Sample 1 Explanation

We can choose $b = \{2, 3\}$ because $2 + 3 + \gcd(2, 3) = \mathrm{lcm}(2, 3)$.

Data Range and Constraints

This problem uses batched testing.

• Subtask 1 (5 points): $n \leq 2$;
• Subtask 2 (20 points): $n \leq 17$;
• Subtask 3 (15 points): $a_i \leq 2 \times 10^3$;
• Subtask 4 (15 points): $n \leq 2 \times 10^3$;
• Subtask 5 (10 points): $n \leq 5 \times 10^4$;
• Subtask 6 (10 points): $a_i \leq 10^7$;
• Subtask 7 (25 points): No additional constraints.

For $100\%$ of the data, $1 \leq n \leq 3 \times 10^5$, $1 \leq a_i \leq 10^9$.

Help/Hints

$\gcd$ stands for Greatest Common Divisor, and $\mathrm{lcm}$ stands for Least Common Multiple.

Source

【LGR-075】Luogu August Monthly Contest II Div.2 & SWTR-06 & EZEC Round 3.

Idea, solution, and data by Alex_Wei.

见题面 Input 部分

见题面 Output 部分