阻止 sigmoid114！

题目描述

什么，sigmoid114 要去开启疯狂做题模式了吗？不，你必须要阻止他。

现在你召集了 $n$ 名同学，每名同学都有一个属性值，你可以让他们按照你需要的某种顺序站在 sigmoid114 面前的 $n$ 个位置，从而起到阻挡作用。假设第 $i$ 个位置同学的属性值为 $a_i$ 。

每个位置都会产生一个阻力，第 $i$ 个位置的阻力 $f(i)$ 由前 $i$ 个位置的同学决定，大小为 $f(i)=\gcd(a_1,a_2,\dots,a_i)$，也就是前 $i$ 名同学属性值的最大公因数，特别地，$f(1)=a_1$。

那么 sigmoid114 受到的总阻力为：

$$ F=\sum_{i=1}^nf(i) $$

你需要确定某种顺序从而最大化 $F$ ，请你求出这个最大值。

快来个人阻止 sigmoid114 啊！

输入

第一行一个不超过 $10^{6}$ 的正整数 $n$。

第二行 $n$ 个不超过 $10^{6}$ 的正整数，分别表示 $n$ 名同学的属性值。

输出

一个数 $F$ 。

输入样例 1

3
2 4 2

输出样例 1

8

输入样例 2

6
1 1 4 5 1 4

输出样例 2

12

样例解释

样例 1 可以重排为 $4,2,2$ ，此时 $f(1)=4,f(2)=\gcd(4,2)=2,f(3)=\gcd(4,2,2)=2$ ，故阻力为 $F=4+2+2=8$ ，并且没有别的排列方式比这个更大。

Author: sigmoid114