有$$$n$$$渔民刚刚钓鱼回来。第 $$$i$$$ 渔夫捕获了一条 $$$a_i$$$ 大小的鱼。
渔民会选择一些顺序来告诉他们捕获的鱼的大小(该顺序只是大小 $$$n$$$ 的排列)。然而,他们并不完全诚实,他们可能会“增加”他们捕获的鱼的大小。
正式地,假设渔民选择的顺序是 $$$[p_1, p_2, p_3, \dots, p_n]$$$。令 $$$b_i$$$ 为订单中第 $$$i$$$ 渔民将告诉其他渔民的值。 $$$b_i$$$ 的值选择如下:
- 订单中的第一个渔夫只是诚实地告诉他捕获的鱼的实际大小,因此 $$$b_1 = a_{p_1}$$$;
- 每个其他渔夫都想告诉一个值,该值严格大于前一个渔夫告诉的值,并且可以被渔夫捕获的鱼的大小整除。因此,对于 $$$i > 1$$$,$$$b_i$$$ 是严格大于 $$$b_{i-1}$$$ 并能被 $$$a_{p_i}$$$ 整除的最小整数。
例如,令 $$$n = 7$$$,$$$a = [1, 8, 2, 3, 2, 2, 3]$$$。如果选择的顺序是 $$$p = [1, 6, 7, 5, 3, 2, 4]$$$,则:
- $$$b_1 = a_{p_1} = 1$$$;
- $$$b_2$$$是能被$$$2$$$整除且大于$$$1$$$的最小整数,即$$$2$$$;
- $$$b_3$$$是能被$$$3$$$整除且大于$$$2$$$的最小整数,即$$$3$$$;
- $$$b_4$$$是能被$$$2$$$整除且大于$$$3$$$的最小整数,即$$$4$$$;
- $$$b_5$$$是能被$$$2$$$整除且大于$$$4$$$的最小整数,即$$$6$$$;
- $$$b_6$$$是能被$$$8$$$整除且大于$$$6$$$的最小整数,即$$$8$$$;
- $$$b_7$$$ 是可被 $$$3$$$ 整除且大于 $$$8$$$ 的最小整数,即 $$$9$$$。
你必须以产生尽可能小的 $$$\sum\limits_{i=1}^{n} b_i$$$ 的方式选择渔民的顺序。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 1000$$$) — 渔民的数量。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$)。
输出
打印一个整数 — 通过最优选择渔民顺序可以获得 $$$\sum\limits_{i=1}^{n} b_i$$$ 的最小可能值。
示例
输入 #1
7 1 8 2 3 2 2 3
输出 #1
33
输入 #2
10 5 6 5 6 5 6 5 6 5 6
输出 #2
165