Bạn được cung cấp một mảng kích thước \(N\). Hãy sắp xếp lại mảng theo cách sao cho tổng của các GCD (ước số chung lớn nhất) trên tất cả các prefix không rỗng của mảng là lớn nhất.

GCD (ước số chung lớn nhất) là số lớn nhất chia hết bất kỳ tập số nào mà không để lại số dư.

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

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

Định dạng đầu ra

• In ra kết quả — tổng lớn nhất có thể của tất cả GCD của các prefix trong mảng đã được sắp xếp lại.

Ràng buộc

• \(1 \le N \le 20\)
• \(1 \le A_i \le 10^9\)

Input 1

3
12 8 6

Output 1

20

Giải thích

Sắp xếp mảng thành 12 6 8. Với cách sắp xếp đó thì tổng GCD of prefix sẽ là gcd(12)+gcd(12,6)+gcd(12,6,8). Đây chính là tổng lớn nhất 20.