Hạo được cung cấp một mảng \(A\) gồm \(N\) số nguyên, trong đó \(N\) là số chẵn.

Trong mỗi lượt chơi, Hạo có thể chọn hai số bất kỳ từ mảng và xóa chúng.

Điểm mà Hạo nhận được ở mỗi lượt sẽ là \(gcd(num1, num2) \times round\), trong đó:

• \(num1\) và \(num2\) là hai số mà Hạo đã chọn.
• \(round\) là lượt chơi hiện tại (bắt đầu từ \(1\) và tăng dần sau mỗi lượt).
• Tổng điểm của Hạo là tổng điểm cô đạt được ở tất cả các lượt chơi.

Hãy xác định tổng điểm tối đa mà Hạo có thể đạt được.

Ràng buộc

• \(1 \le N \le 20\)
• \(1 \le A[i] \le 10^9\)

Định dạng đầu vào

• Dòng đầu tiên chứa một số nguyên \(N\), biểu thị độ dài của mảng \(A\).
• Dòng thứ hai chứa \(N\) số nguyên dương cách nhau bởi dấu cách, là các phần tử của mảng \(A\).

Định dạng đầu ra

• Một số nguyên biểu thị tổng điểm tối đa mà Hạo có thể đạt được.

Input 1

4
3 4 9 5

Output 1

7

Giải thích

• Round1 : select \(num1 = 4, num2=5\) . \(gcd(num1,num2) \times round = 1 \times 1=1\).
• Round2 : select \(num1 = 3, num2=9\) . \(gcd(num1,num2) \times round = 3 \times 2=6\).
• Maximum total score = \(6+1 = 7\)