Background

Special for beginners, ^_^

Description

徐老师很喜欢gcd和sum，现在他想在数组a中挑选一个非空子序列b，然后定义这个子序列的权值为gcd(b)*sum(b)，求权值最大的子序列

Format

Input

第一行输入一个$n(1 \leq n \leq 10^5)$，表示数组长度

第二行输入 $n$ 个整数 $a_i(1 \leq a_i \leq 10^6)$，表示数组中的元素

Output

输出一个数，表示最大权值

Samples

3
1 2 4

16

Limitation

1s, 1024KiB for each test case.