Cho một dãy gồm \(n (1 \le n \le 20)\) số nguyên dương, mỗi số có giá trị không vượt quá \(10^9\)

Gọi \(g(i)\) là ước chung lớn nhất của \(i\) số đầu tiên của dãy.

Hãy sắp xếp lại dãy số để \(S = g(1) + g(2) + g(3)... + g(n)\)

Input

• Dòng đầu ghi số \(n\)
• Dòng thứ hai ghi \(n\) số cho biết dãy số.

Output

• Một số là giá trị \(S\) lớn nhất tìm được.

Example

Sample input

3
6 8 12

Sample output

20