Today is YQH's birthday, and she received a sequence of $n$ positive integers $a_1, a_2, \dots, a_n$ as a birthday gift.
However, YQH is not satisfied with this sequence because it might not be valid.
Specifically, a sequence is valid if and only if there exists an integer $k > 1$ such that every element in the sequence is a multiple of $k$.
To make YQH satisfied, you need to find a subsequence of $a_1, a_2, \dots, a_n$ that is valid. $b_1, b_2, \dots, b_m$ is called a subsequence of $a_1, a_2, \dots, a_n$ if and only if it can be obtained by deleting zero or more elements from $a_1, a_2, \dots, a_n$.
There may be many valid subsequences, so YQH only wants you to find the maximum possible sum of a valid subsequence. Note that the subsequence can be empty, and the empty set is considered valid.
Input
The first line contains a positive integer $n$.
The next $n$ lines each contain a positive integer. The number on the $i$-th line represents $a_i$.
Output
Output a single integer representing the answer.
Examples
Input 1
4 1 1 1 1
Output 1
0
The only valid subsequence is the empty set.
Input 2
6 1 2 3 4 5 6
Output 2
12
One valid subsequence is $[2, 4, 6]$, as they all have a factor of $2$. It can be proven that there is no valid subsequence with a larger sum.
Input 3
10 28851 8842 9535 2311 25337 26467 12720 10561 8892 6435
Output 3
56898
Input 4
See ex_divisor4.in/ex_divisor4.ans in the provided files.
Input 5
See ex_divisor5.in/ex_divisor5.ans in the provided files.
Subtasks
| Subtask ID | $n \le$ | $a_i \le$ | Special Constraints | Score |
|---|---|---|---|---|
| $1$ | $18$ | $10^9$ | None | $20$ |
| $2$ | $1000$ | $10^5$ | $20$ | |
| $3$ | $10^9$ | A | $20$ | |
| $4$ | None | $40$ |
Special Constraint A: It is guaranteed that all $a_i$ are prime numbers.
For all data, it is guaranteed that $1 \le n \le 1000$ and $1 \le a_i \le 10^9$.