该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Special for beginners, ^_^

Description

徐老师得到了一个数组a，他可以选择任意两个数字$a_i$和$a_j$，然后把它们都换成$gcd(a_i,a_j)$，徐老师进行无数次操作，他想最小化数组的和，请你帮他计算一下

Format

Input

第一行一个数字$n(1 \leq n \leq 10^5)$，表示数组的大小

第二行n个数字$a_i(1 \leq a_i \leq 10^9)$，表示数组的元素

Output

一个整数，表示数组和的最小值

Samples

5
1 2 3 4 5

5

Limitation

1s, 1024KiB for each test case.