Problem Description

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

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

• If you do not know what $\gcd$ and $\mathrm{lcm}$ are, you can click the link in the "Help / Hint" section at the bottom.

Little A wants the sum of the chosen numbers to be as large as possible. Please output this maximum value.

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 one line with one integer, representing the answer.

4
4 3 2 1

5

10
6 7 18 4 17 10 9 1 3 8

19

3
123456789 234567890 123456789

246913578

Hint

"Sample 1 Explanation"

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

"Constraints and Notes"

This problem uses bundled testdata.

• Subtask 1 (5 points): $n\leq2$.
• 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 special constraints.

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

"Help / Hint"

$\gcd$ means greatest common divisor, and $\mathrm{lcm}$ means least common multiple.

"Source"

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

idea & solution & data by Alex_Wei.

Translated by ChatGPT 5