Public Judge

pjudge

Time Limit: 1 s Memory Limit: 512 MB Total points: 100

# 21693. 【NOIP Round #3】因子

Statistics

题目描述

今天是 YQH 的生日,她得到了一个长度为 $n$ 的正整数序列 $a_1,a_2,\dots,a_n$ 作为生日礼物。

然而,YQH 并不对这个序列满意,因为这个序列可能不合法。

具体地,一个序列合法,当且仅当存在一个大于 $1$ 的整数 $k$,使得序列里每个元素都是 $k$ 的倍数。

为了让 YQH 满意,你需要找到一个 $a_1,a_2,\dots,a_n$ 的子序列,使得这个子序列是合法的。$b_1,b_2,\dots,b_m$ 称为 $a_1,a_2,\dots,a_n$ 的子序列当且仅当,你可以从 $a_1,a_2,\dots,a_n$ 删去若干个(可以是 $0$ 个)元素后得到 $b_1,b_2,\dots,b_m$。

符合条件的子序列可能很多,所以 YQH 只想要你找到,总和最大的合法子序列的总和。注意,子序列可以取空集,且空集是合法的。

输入格式

第一行一个正整数 $n$。

接下来 $n$ 行,每行一个正整数。第 $i$ 行的数表示 $a_{i-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\le$ $a_i\le$ 特殊限制 分值
$1$ $18$ $10^9$ $20$
$2$ $1000$ $10^5$ $20$
$3$ $10^9$ A $20$
$4$ $40$

特殊限制A:保证所有 $a_i$ 都是质数。

对于所有数据,保证 $1\le n\le 1000,1\le a_i\le 10^9$。