Non-Trivial Common Divisor

Interview

Time limit3sMemory limit512 MB

Summary

Pick a subset of the given numbers that all share a common divisor greater than 1, maximizing the subset's sum.

Level: Medium6 of 10
Topics: Number theory, Hash map, Greedy, Math
Solved: No attempts yet

Problem

You are given a sequence $A$ of $N$ positive integers. You may remove any numbers from the sequence to make it "friendly". A sequence is friendly if there is an integer $k$ ( $k>1$ ) such that every number in the sequence is a multiple of $k$ . Since the empty sequence is friendly, it is always possible to make the initial sequence friendly.

There may be several ways to make the sequence friendly, so you decide to maximize the sum of all numbers in the friendly sequence. Compute the maximum possible sum of all numbers in a friendly sequence obtained from the initial sequence.

Input

The input consists of a single test case formatted as follows. The first line contains a single integer $N$ ( $1 \le N \le 1000$ ). The $(i+1)$ -st line contains an integer $A_i$ ( $1 \le A_i \le 10^9$ ) for $1 \le i \le N$ .

Output

Print the maximum sum of all numbers in a friendly sequence obtained from the initial sequence.

Examples5

Example 1
Input
```
6
1
2
3
4
5
6
```
Expected output
```
12
```
Example 2
Input
```
3
173
1733
111733
```
Expected output
```
111733
```
Example 3
Input
```
4
1
1
1
1
```
Expected output
```
0
```

Example 4

Input

Expected output

9999999990

Example 5
Input
```
1
999999999
```
Expected output
```
999999999
```