자명하지 않은 공약수

면접 대비

시간 제한3초메모리 제한512 MB

요약

주어진 수들 중에서 1보다 큰 공약수를 모두 공유하는 부분집합을 골라 그 합이 최대가 되도록 한다.

난이도: 보통10점 중 6점
유형: 정수론, 해시맵, 그리디, 수학
정답자: 아직 제출이 없습니다

문제

길이가 $N$ 인 양의 정수 수열 $A$ 가 주어진다. 수열에서 몇 개의 수를 지워 수열을 "친화적"으로 만들 수 있다. 어떤 정수 $k$ ( $k>1$ )가 존재하여 수열의 모든 수가 $k$ 의 배수이면 그 수열을 친화적이라고 한다. 빈 수열은 친화적이므로, 처음 수열을 친화적으로 만드는 것은 항상 가능하다.

수열을 친화적으로 만드는 방법은 여러 가지일 수 있다. 그래서 친화적 수열에 있는 모든 수의 합을 최대로 만들려고 한다. 처음 수열에서 얻을 수 있는 친화적 수열의 모든 수 합의 최댓값을 계산하시오.

입력

입력은 하나의 테스트 케이스로 이루어지며 다음과 같은 형식이다. 첫째 줄에 정수 $N$ ( $1 \le N \le 1000$ )이 주어진다. $i+1$ 번째 줄에 정수 $A_i$ ( $1 \le A_i \le 10^9$ )가 주어진다 ( $1 \le i \le N$ ).

출력

처음 수열에서 얻을 수 있는 친화적 수열의 모든 수 합의 최댓값을 출력한다.

예제5

예제 1
입력
```
6
1
2
3
4
5
6
```
예상 출력
```
12
```
예제 2
입력
```
3
173
1733
111733
```
예상 출력
```
111733
```
예제 3
입력
```
4
1
1
1
1
```
예상 출력
```
0
```

예제 4

입력

예상 출력

9999999990

예제 5
입력
```
1
999999999
```
예상 출력
```
999999999
```