리본

면접 대비

시간 제한2초메모리 제한256 MB

요약

양쪽 끝의 오염된 1인치를 버린 뒤 모든 롤을 남김없이 자를 수 있는 가장 긴 공통 조각 길이와 전체 조각 개수를 구합니다.

난이도: 쉬움10점 중 3점
유형: 정수론
정답자: 아직 제출이 없습니다

문제

Jim은 생일 파티에 쓸 리본 매듭을 아주 많이 만들려고 한다. 그래서 색이 서로 다른 리본 롤을 여러 개 샀다. 막상 매듭을 만들려고 보니 모든 롤의 처음 1인치와 마지막 1인치는 더러워져서 쓸 수 없었다. 매듭을 만들려면 리본을 잘라야 하고, 조각은 최대한 길게 잘라야 한다. 단, 잘라낸 조각은 모두 길이가 같아야 한다.

길이가 $k$ 인 롤에서 쓸 수 있는 리본은 양쪽 1인치를 뺀 $k - 2$ 인치다. 모든 롤을 이 공통 길이로 남는 부분 없이 잘라야 한다.

입력

입력은 표준 입력으로 주어지고 여러 줄로 이루어진다. 각 줄은 롤의 개수 $n$ 으로 시작하며, $2 \le n \le 10$ 이다. 그 뒤에 각 롤의 리본 길이 $k$ 가 $n$ 개 주어지며, $5 \le k \le 500000$ 이다. 한 줄에 있는 수는 모두 공백 하나로 구분된다. 입력이 끝날 때까지 각 줄을 처리한다.

출력

입력의 각 줄마다 두 정수를 공백 하나로 구분해 한 줄에 출력한다. 첫 번째 수는 잘라낸 조각 하나의 길이이고, 두 번째 수는 Jim이 만들 수 있는 매듭의 총 개수다.

예제3

예제 1

입력

3 14 23 29
2 11 29
4 200 120 180 500

예상 출력

3 20
9 4
2 496

예제 2
입력
```
3 6 8 10
```
예상 출력
```
2 9
```
예제 3
입력
```
2 5 6
```
예상 출력
```
1 7
```