Problem 1B. 提高攻击力

Limits

时间限制：2000ms

内存限制：256MB

Background

这天小周穿越到了一个游戏世界里，在这个世界里，需要找到各种物品提升自己的攻击力才能存活下去。小周在一番搜索后，找到了 \(n\) 件可以提升自己攻击力的物品的位置。小周通过各种渠道，在发现第 \(i\) 件物品位置的同时，也知道了第 \(i\) 件物品 "理论上" 可以提升自己 \(a_i\) (\(a_i > 0\))的攻击力。就在小周打算去找这 \(n\) 件物品提升自己攻击力的时候，一旁的村民小季告诉了他这个世界的物品使用规则。

Description

在这个世界中，单独使用一个物品是没有任何效果的，增加的攻击力为 \(0\)；使用不同物品之间又是有冲突的，如果使用了多个物品提升自己的攻击力，那么最后能提升的攻击力并不是理论值简单的加在一起。具体来说，如果选择了 \(k\) (\(k>1\))件物品来提升自己的攻击力，他们理论能提升的攻击力分别为 \(a_1, a_2, ...,a_k\) .当 \(gcd(a_1, a_2, ..., a_k)=1\)时，这 \(k\) 个物品也将起不到任何提升攻击力的作用，即增加的攻击力为 \(0\)，当 \(gcd(a_1, a_2, ..., a_k)>1\) 时，增加的攻击力为 \(gcd(a_1, a_2, ..., a_k) \times k\).

听完讲解后，小周想知道这 \(n\) 件物品最多能让他增加多少攻击力，于是他打算编程来解决这个问题。

Input

第一行两个整数 \(n\) , 含义见描述；

第二行 \(n\) 个整数，第 \(i\) 个数代表使用第 \(i\) 个物品理论上能提升的攻击力。

Output

输出一行，表示最大能增加的攻击力。

Samples

Sample Input 1

3
2 3 4

Sample Output 1

4

提示：使用第 \(1\) 件物品和第 \(3\) 件物品，可以提升 \(2 * gcd(2, 4) = 2 \times 2 = 4\) 点攻击力；其他无论怎么选择，增加的攻击力都是 \(0\).

Sample Input 2

5
2 3 4 6 7

Sample Output 2

6

Data range

对于50% 数据，\(1 \leq n \leq 20\)，对于 100% 数据，\(1 \leq n \leq 10^5\)。

每个物品理论上能增加的攻击力满足 \(1 \leq a_i \leq 10^5\) 。

注意， 答案可能超出32位整数的范围 。