题目描述

Tomorrow Programming School 的机器人实验室会批量生产微型机器人。为了执行各种复杂任务，机器人经常组成团队。

在任务开始前，一个团队需要测量自己的战斗力。团队中的机器人首先选出一台机器人担任队长，然后所有机器人在队长身后排成一列。

除队长外，每台机器人都会向队长报告一个数值：它自身高度与排在它正前方的相邻机器人高度的最大公约数。这个数值代表两台机器人在执行任务时的连接强度。

队长把所有报告的数值相加，并把总和定义为这个团队的战斗力。

每台机器人的高度均以厘米为单位，并且是 $1$ 到 $20$ 之间的整数。

团队的战斗力取决于机器人的排列顺序。队长的选择同样会影响排列，因此团队中的任意机器人都可以被选为队长。

机器人希望通过选择合适的队长并安排合适的排列顺序，使团队战斗力最大。

请计算能够获得的最大团队战斗力。

输入格式

第一行包含一个整数 $N$：

表示团队中的机器人数量。

第二行包含 $N$ 个以空格分隔的整数

其中

表示所有机器人的高度。

输出格式

输出一个整数，表示该团队能够获得的最大战斗力。

样例

输入

7
2 3 12 4 6 4 3

输出

22