H. 数字删除

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

Rhodoks 有 张卡片,第 张卡片上有一个点数 。 由于 Rhodoks 的行政顾问 Sheauhaw 具有强迫症特质,Sheauhaw 认为互素是不好的特质,于是他希望拿走一些卡片,令 Rhodoks 手上剩下的所有卡片的点数的最大公因数不为 。 Rhodoks 喜欢大的东西,所以希望这些点数之和尽可能地大。请问,在满足 Sheauhaw 的要求的情况下,剩余卡片的点数之和最大为多少?

如果 Rhodoks 手上只有一张卡片点数为 ,那么最大公因数就是 。 如果 Rhodoks 手上没有卡片,那么最大公因数就是 ,也是满足条件的。

输入格式

第一行一个正整数

下面 行,每行一个正整数

输出格式

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

样例

样例输入1

6
1
2
3
4
5
6

样例输出1

12

样例输入2

3
173
1733
111733

样例输出2

111733

样例输入3

4
1
1
1
1

样例输出3

0

样例输入4

10
999999999
999999999
999999999
999999999
999999999
999999999
999999999
999999999
999999999
999999999

样例输出4

9999999990

样例输入5

10
28851
8842
9535
2311
25337
26467
12720
10561
8892
6435

样例输出5

56898

数据范围与提示