题目描述

小可面前有一排$n$个格子，编号从$1$到$n$，每个格子上都有一个数字$a$，最初所有格子都是白色的，他现在希望将所有格子都染红。具体的，他可以做任意多次下方的操作：

• 将他目前所在的格子染红，花费为 $a_{i}$；
• 从红色的格子瞬移到任意一个红色格子$j$，花费为$0$；
• 从红色的格子瞬移到任意一个白色格子$j$，花费为最小公倍数$lcm (a_{i},a_{j})$。

小可初始时位于1号格子，他想知道将所有的格子都染红，最少需要花费多少，请你帮帮他吧。

输入格式

第一行输入一个整数$n$代表格子数。

第二行输入n个整数$a_1,a_2,...,a_n$,代表每个格子上的数字。

输出格式

输出一个整数，表示最少花费。

样例

4
2 4 6 8

38

提示

样例1解释

一个最佳的染色顺序是$1->2->1->3->1->4$，需要注意的是染色完不一定要返回$1$号点，只是在这里返回$1$号点再前往其他点花费会更少。

数据范围

对于所有测试数据，保证：$1 \leq n \leq 2*10^3$，$1 \leq a_i \leq 2*10^3$。