题目描述
今天是 YQH 的生日，她得到了一个长度为 n 的正整数序列 a1,a2,…,an 作为生日礼物。
然而，YQH 并不对这个序列满意，因为这个序列可能不合法。
具体地，一个序列合法，当且仅当存在一个大于 1 的整数 k，使得序列里每个元素都是 k 的倍数。
为了让 YQH 满意，你需要找到一个 a1,a2,…,an 的子序列，使得这个子序列是合法的。b1,b2,…,bm 称为 a1,a2,…,an 的子序列当且仅当，你可以从 a1,a2,…,an 删去若干个（可以是 0 个）元素后得到 b1,b2,…,bm。
符合条件的子序列可能很多，所以 YQH 只想要你找到，总和最大的合法子序列的总和。注意，子序列可以取空集，且空集是合法的。
输入格式
第一行一个正整数 n。
接下来 n 行，每行一个正整数。第 i 行的数表示 ai−1。
输出格式
输出一个整数表示答案。
样例
输入1
4 1 1 1 1
输出1
0
唯一合法的子序列是空集。
输入2
6 1 2 3 4 5 6
输出2
12
一种合法的子序列为 [2,4,6]，它们都有因子 2，可以证明没有总和更大的合法子序列。
输入3
10 28851 8842 9535 2311 25337 26467 12720 10561 8892 6435
输出3
56898
样例输入/输出 4
见下发文件中的 ex_divisor4.in/ex_divisor4.ans。
样例输入/输出 5
见下发文件中的 ex_divisor5.in/ex_divisor5.ans。
数据范围
| 子任务编号 | n≤ | ai≤ | 特殊限制 | 分值 |
|---|---|---|---|---|
| 1 | 18 | 109 | 无 | 20 |
| 2 | 1000 | 105 | 20 | |
| 3 | 109 | A | 20 | |
| 4 | 无 | 40 |
特殊限制A：保证所有 ai 都是质数。
对于所有数据，保证 1≤n≤1000,1≤ai≤109。