题目描述

你正在参加国际构造排列大赛(International Construct Permutation Contest, ICPC)，设 $\left[ a_i \right]$ 是一个一共有 $n$ 项的整数数列。给定数列数字，请你将 $\left[ a_i \right]$ 重新排列为 $\left[ p_i \right]$ 并尝试求出

$$S=\sum_{i=1}^{n-1}\operatorname{lcm} (p_i,p_{i+1})$$

的最小值。

输入描述

第一行输入一个整数 $n$ 表示数列长度，满足 $2\leqslant n \leqslant 20$。

第二行输入 $n$ 个正整数 $a_i$，满足 $1\leqslant a_i\leqslant 10^8$。

输出描述

输出一个数，表示 $S$ 的最小值。

样例

6
1 1 4 5 1 4

15

4
114 514 1919 810

235074

9
3 1 4 1 5 9 2 6 5

40

注释

对于第三组样例，满足条件的一种情况为：$\left[ 9,3,6,2,4,1,1,5,5 \right]$。