Maximizing Sum with 2:3 Pairing

Little A has a sequence of n integers \(a_1, a_2, \dots, a_n\). He wants to select a non-empty subset \(b\) from these numbers so that the following condition holds: for every element \(b_i\) in the chosen subset that is not the maximum, there exists some \(b_j\) with \(b_j > b_i\) satisfying

[ b_i + b_j + \gcd(b_i, b_j) = \mathrm{lcm}(b_i, b_j). ]

If you are not familiar with \(\gcd\) and \(\mathrm{lcm}\), please refer to the help section.

It can be proved that the above equality holds if and only if \(b_i = 2d\) and \(b_j = 3d\) for some positive integer \(d\). In other words, every number you select (except the unique maximum) must be of the form \(2d\) and its corresponding partner \(3d\) must also be selected — and among these, only one number (the largest value) is allowed to not have a partner.

Your task is to choose a valid subset \(b\) so that the sum of its elements is maximized. Note that a subset consisting of a single number is always valid.

inputFormat

The first line contains an integer \(n\) (\(1 \le n \le 10^5\)), representing the length of the sequence. The second line contains \(n\) space-separated integers \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^9\)).

outputFormat

Output a single integer, the maximum sum achievable by selecting a valid subset.

sample

3
2 3 3

5