Shil wants to gift his girlfriend a new year present of N natural numbers. However, he has not decided the order in which he should give them. He wants to gifts these numbers to his girlfriend in the order having highest beauty. Beauty of sequence of N numbers A[1],A[2],A[3]...A[N] is defined as summation of GCD( A[i] , A[i+1] ) where 1 < i < = N. Beauty = summation GCD(A[i],A[i+1]) where 1 <= i < N. As being a good programmer you should help Shil to determine maximum possible beauty in any possible ordering of these numbers.Given N natural numbers,you should find the maximum beauty possible.Note that you should gift all the given numbers.You are only allowed to change the order of these numbers to calculate maximum possible beauty.

Input
First line consists of a single integer N .
Second line consists of N natural numbers

Output
Reorder these numbers in such a way a way such that beauty of sequence is maximum and output this maximum beauty possible.

Constraints
2<= N <= 15
A[i] <= 10^9

Note
GCD stands for greatest common divisor.