You are given \(N\) cities and the \(i^{th}\) city contains \(a[i]\) blocks. If you want to build a road between \(i^{th}\) and \(j^{th}\) cities (\(i \neq j\)), then the number of blocks needed is \(gcd(a[i],a[j])\). Here gcd is the greatest common divisor. You have to build roads in such a way that any person can go from any city to another city in exactly one way, not more than one way between two cities. You have to maximize the total number of blocks used to build roads.

Input format

• The first line contains \(N\) denoting the number of cities.
• The second line contains \(N\) integers, \(a[1], a[2],...,a[N] \) where \(a[i]\) is the number of blocks in the \(i^{th}\) city.  

Output format

Print a maximum number of blocks used to build roads in such a way the provided condition is satisfied.

Constraints