Tiết dạy thao giảng chào mừng ngày nhà giáo Việt Nam \(20/11\) ở lớp của bé Bình An thật thú vị. Tiết học vận dụng tìm ước chung lớn nhất của hai số nguyên, Bình An rất ấn tượng với tiết đó của thầy T. Bé về nhà háo hức kể chuyện lại với anh trai về tiết học ấy.

Theo mô tả của bé Bình An: Thầy T cho \(n\) bạn học sinh trong lớp đứng thành một hàng ngang, mỗi bạn cầm trên tay một số nguyên dương \(a_1, a_2, ..., a_n.\) Các bạn còn lại sẽ chia thành các đội chơi, mỗi đội chơi gồm \(4\) bạn. Nhiệm vụ của mỗi bạn trong mỗi đội chơi là phải phối hợp với nhau và cùng tìm ra \(4\) vị trí \(1 \leq i < j < k < l \leq n\), sau đó tính \(GCD(a_i, a_j) + GCD(a_k, a_l)\) \((*)\). Trong đó \(GCD(x, y)\) là ký hiệu tìm ước chung lớn nhất của hai số nguyên dương \(x, y\). Đội chơi nào tìm được kết quả của biểu thức \((*)\) lớn nhất là đội chơi dành chiến thắng.

Yêu cầu:

Bạn hãy lập trình tìm kết quả lớn nhất của biểu thức \((*)\).

Input

• Dòng đầu gồm số nguyên dương \(n\)
• Dòng thứ hai gồm \(n\) phần tử nguyên dương \(a_1, a_2, ..., a_n (a_i \leq 10^9)\)

Output

• In ra kết quả bài toán là giá trị \(GCD(a_i, a_j) + GCD(a_k, a_l)\) lớn nhất.

Sample Input

6
8 12 4 20 30 15

Sample Output

19

Giải thích

• \((i, j, k, l) = (1, 3, 5, 6)\)

Ràng buộc

• \(50\%\) số test tương ứng với \(n \leq 50.\)
• \(50\%\) số test tiếp theo tương ứng với \(n \leq 2000.\)