题目描述

小可是一名探险家，正在闯过一个神秘的走廊。这条走廊共有 $n$ 个房间，编号从 $1$ 到 $n$。每个房间的门口都刻有一个魔法数字 $a_i$，房间初始均为 “未解锁” 状态。小可的目标是解锁所有房间。

他拥有一种特殊的魔法能力，可以执行以下任意多次操作：

1. 解锁当前房间：花费的魔力值等于该房间的数字 $a_i$；
2. 自由传送：在已解锁的房间之间传送不需要任何花费；
3. 破门传送：从已解锁的房间传送到一个未解锁的房间 j，需要消耗与两房间数字相关的魔力，数值为 $lcm(a_i,\ a_j)$。（$lcm$ 是最小公倍数）

小可最初位于第 $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$。