题目描述

小 A 有一个长度为 $n$ 的序列 $a_1,a_2,\cdots,a_n$。

他想从这些数中选出一些数 $b_1,b_2,\cdots,b_k$ 满足：对于所有 $i\ (1\leq i\leq k)$，$b_i$ 要么是序列 $b$ 中的最大值，要么存在一个位置 $j$ 使得 $b_j>b_i$ 且 $b_i+b_j+\gcd(b_i,b_j)=\mathrm{lcm}(b_i,b_j)$。

• 如果你不知道 $\gcd$ 和 $\mathrm{lcm}$ 是什么，可以点击最底部的「帮助/提示」部分的链接。

小 A 想让选出的数之和尽量大。请求出这个最大值。

输入格式

第一行一个整数 $n$，表示序列的长度。

第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$。

输出格式

输出一行一个整数表示答案。

4
4 3 2 1

5

10
6 7 18 4 17 10 9 1 3 8

19

3
123456789 234567890 123456789

246913578

提示

「样例 1 说明」

可以选择 $b=\{2,3\}$，因为 $2+3+\gcd(2,3)=\mathrm{lcm}(2,3)$。

「数据范围与约定」

本题采用捆绑测试。

• 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）：无特殊限制。

对于 $100\%$ 的数据，$1\leq n\leq 3\times 10^5$，$1\leq a_i\leq 10^9$。

「帮助/提示」

$\gcd$ 表示最大公约数，$\mathrm{lcm}$ 表示最小公倍数。

「来源」

【LGR-075】洛谷 8 月月赛 II Div.2 & SWTR-06 & EZEC Round 3。

idea & solution & data by Alex_Wei。