최대공약수로 잇기

어느 대학교 학과에 학생 $n$명이 입학했습니다. 학생들은 서로 잘 모르기 때문에 앞으로 있을 시험과 평가 소식을 빠르고 확실하게 주고받을 방법이 필요합니다. 그래서 학생들은 새로운 바이트랜드 메신저에서 여러 개의 대화를 만듭니다. 각 대화에는 정확히 두 명의 학생이 참여합니다. 정보는 다음과 같이 퍼집니다. 한 학생이 곧 있을 시험 소식을 알게 되면, 그 학생은 같은 조 동기들과 나눈 모든 대화에 이 메시지를 보냅니다. 그다음 처음으로 메시지를 받은 사람들이 자신이 참여한 모든 대화에 메시지를 보내고, 이런 식으로 계속 이어집니다.

반장은 모든 학생이 메시지를 최소 한 번 받도록 대화 네트워크를 구성하려 합니다. 대화의 수는 가능한 한 적어야 합니다. 각 학생 $i$에게는 정수 $a_i$가 주어집니다. 학생 $u$와 $v$ 사이에 만든 대화의 점수는 $\gcd(a_u, a_v)$입니다. 반장은 모든 대화 점수의 합이 최대가 되기를 원합니다. 가능한 최대 점수 합을 구하세요.

첫째 줄에 학생 수 $n$ ($1 \le n \le 100\,000$)이 주어집니다. 둘째 줄에는 양의 정수 $a_i$ ($1 \le a_i \le 1\,000\,000$) $n$개가 주어집니다.

대화의 수가 최소인 네트워크 중에서 반장이 만들 수 있는 점수 합의 최댓값을 한 줄에 출력합니다.

첫 번째 예제에서 최적해는 학생 쌍 (1, 2), (2, 3), (2, 4), (4, 5) 사이에 대화를 만드는 것입니다. 이 네트워크의 점수 합은 $1 + 1 + 2 + 1 = 5$입니다.