P6786 "SWTR-6" GCD & LCM

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.

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

**"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](https://baike.baidu.com/item/%E6%9C%80%E5%A4%A7%E5%85%AC%E7%BA%A6%E6%95%B0/869308?fr=aladdin), and $\mathrm{lcm}$ means [least common multiple](https://baike.baidu.com/item/%E6%9C%80%E5%B0%8F%E5%85%AC%E5%80%8D%E6%95%B0/6192375?fr=aladdin). **"Source"** [【LGR-075】Luogu August Monthly Contest II Div.2 & SWTR-06 & EZEC Round 3](https://www.luogu.com.cn/contest/33190). idea & solution & data by [Alex_Wei](https://www.luogu.com.cn/user/123294). Translated by ChatGPT 5