问题描述

小C定义了一个长度为 $k$ 的数组 $\{a_1,a_2,...,a_k\}$ 的权值为 $gcd(a_1,a_2,...,a_k) \times (a_1+a_2+...+a_k)$ 。

现在小L给定了一个长度为 $n$ 的数组 $\{a_1,a_2,...,a_n\}$，小C可以从中挑选一个子序列带走，小C希望挑选的子序列非空且权值尽可能大。

【名词解释】

$\operatorname{gcd}(a_1,a_2,\ldots,a_k)$ ：即求解 $a_1,a_2,\ldots,a_k$ 的最大公约数，指所有整数共有约数中最大的一个。例如，$12$、$18$ 和 $30$ 的公约数有 $1$，$2$，$3$，$6$，其中最大的约数是 $6$ ，因此 $\gcd(12,18,30)=6$。

非空子序列：从原序列中删除任意个（可以为零，但必须保留至少一个）元素后，保持剩余元素相对顺序不变得到的新序列。

输入格式

第一个整数 $n$ ，表示数组的长度。

接下来一行一个 $n$ 个整数 $a_i$ ，相邻的元素以空格隔开。

输出格式

输出最大的权值即可。

样例输入

3
2 6 4

样例输出

36

说明

样例 $1$ 解释

在这个样例中，一共有 $7$ 种不同的子序列选择方案：

$\{2\}$，权值为 $2×2=4$；

$\{6\}$，权值为 $6×6=36$；

$\{4\}$，权值为 $4×4=16$；

$\{2,6\}$，权值为 $gcd(2,6)×(2+6)=2×8=16$；

$\{2,4\}$，权值为 $gcd(2,4)×(2+4)=2×6=12$；

$\{6,4\}$，权值为 $gcd(6,4)×(6+4)=2×10=20$；

$\{2,6,4\}$，权值为 $gcd(2,6,4)×(2+6+4)=2×12=24$。

综上，权值最大的子序列是 $\{6\}$ ，权值为 $36$。

数据范围

前 $30\%$的数据，$3 \leq n \leq 20$

$100\%$的数据， $3\leq n\leq 10^5， 1 \le a_i \le 10^6$ 。