모든 곡에 맞는 구간

문제

한 음악 스트리밍 서비스는 여러 곡을 같은 길이의 재생 구간으로 나누어 전송한다. 각 곡의 길이는 초 단위의 양의 정수이며, 재생 구간의 길이도 초 단위의 양의 정수로 정한다. 한 곡의 첫 구간은 곡의 시작점에서 시작하고, 다음 구간들은 빈틈이나 겹침 없이 이어진다. 마지막 구간도 앞의 구간들과 길이가 같아야 하므로, 곡의 끝에 짧은 나머지 구간을 붙이거나 무음을 추가하는 방법은 허용하지 않는다. 이번에 전송할 곡은 N개다. 서비스는 이 곡들을 모두 하나의 전송 설정으로 처리하려고 한다. 따라서 선택한 구간 길이는 모든 곡의 길이를 나누어떨어지게 해야 한다. 예를 들어 길이가 18초인 곡은 3초 구간 여섯 개로 나눌 수 있지만, 4초 구간만으로는 정확히 나눌 수 없다. 곡마다 서로 다른 구간 길이를 선택하는 것은 허용하지 않는다. 전송 장치에는 한 구간이 K초를 넘을 수 없다는 제한도 있다. 이 제한을 지키면서 구간 길이를 최대한 길게 정하면 구간을 관리하는 횟수를 줄일 수 있다. 모든 곡을 정확히 나눌 수 있고 K 이하인 구간 길이 중 가장 큰 값을 구하는 프로그램을 작성한다. 같은 길이의 곡이 여러 개 주어질 수 있으며, 그 곡들도 각각 입력에 포함된다. 곡의 순서는 정답에 영향을 주지 않는다. 모든 곡의 길이와 K는 양의 정수이므로 1초 구간은 언제나 사용할 수 있다. 따라서 가능한 구간 길이가 없는 경우는 발생하지 않는다. 구간의 개수나 곡별 분할 결과는 출력하지 않고, 선택한 구간의 길이만 초 단위 정수로 출력한다.

입력

첫째 줄에 정수 N과 K가 공백으로 주어진다. 1 ≤ N ≤ 50,000, 1 ≤ K ≤ 1,000,000이다.
둘째 줄에 각 곡의 길이를 나타내는 정수 A_1, A_2, ..., A_N이 공백으로 주어진다. 모든 i에 대해 1 ≤ A_i ≤ 1,000,000이다.

출력

모든 A_i를 나누어떨어지게 하는 K 이하의 양의 정수 중 최댓값을 출력한다.

3 8
36 60 84

6

4 100
14 25 39 52

1

1 9
20

5

출처: Devin.KR 자체 제작