지하철 승강장 안내 띠

문제

한 지하철역은 승강장의 여러 대기 구역 바닥에 안내 띠를 붙이려고 한다. 대기 구역은 모두 곧은 선분 모양이며, 각 구역의 길이는 센티미터 단위의 양의 정수로 측정되어 있다. 안내 띠는 길이가 같은 조각을 여러 개 이어 붙여 만들며, 모든 대기 구역에서 같은 길이의 조각을 사용한다. 조각의 길이도 센티미터 단위의 양의 정수여야 한다. 각 대기 구역에는 시작점부터 끝점까지 빈틈없이 안내 띠를 붙여야 한다. 조각을 자르거나 서로 겹쳐 붙일 수 없고, 구역의 끝을 넘어가도록 붙일 수도 없다. 따라서 길이가 L인 구역에 길이가 d인 조각을 사용하려면 L이 d로 나누어떨어져야 한다. 서로 다른 구역에서 사용한 조각을 연결하는 일은 없으며, 각 구역은 별도로 완성한다. 준비할 수 있는 조각의 개수에는 제한이 없다. 보관함의 크기 때문에 조각 하나의 길이는 K센티미터 이하여야 한다. 담당자는 붙이는 작업을 줄이기 위해 이 제한 안에서 조각의 길이를 가능한 한 길게 정하려고 한다. 특정 구역만 다른 길이의 조각을 사용하는 것은 허용하지 않는다. 입력된 모든 구역의 길이에 동시에 사용할 수 있어야 한다. 같은 길이의 구역이 여러 개 주어져도 각각 작업 대상에 포함되지만, 조각 길이에 적용되는 조건은 동일하다. 구해야 하는 값은 사용할 조각 한 개의 길이이며 전체 조각의 개수나 남는 길이가 아니다. 길이가 1센티미터인 조각은 모든 정수 길이의 구역에 사용할 수 있고 K도 1 이상이므로 가능한 길이는 항상 존재한다. 구역의 길이들과 보관함 제한을 입력받아 선택할 수 있는 가장 긴 조각의 길이를 구하는 프로그램을 작성한다.

입력

첫째 줄에 대기 구역의 개수 N과 조각 길이의 상한 K가 공백으로 구분되어 주어진다. N과 K는 정수이며 1 ≤ N ≤ 30,000, 1 ≤ K ≤ 1,000,000이다.
둘째 줄에 각 대기 구역의 길이 L_1, L_2, ..., L_N이 공백으로 구분되어 주어진다. 모든 길이는 정수이며 1 ≤ L_i ≤ 1,000,000이다.

출력

모든 구역의 길이를 나누어떨어지게 하는 양의 정수 중 K 이하인 가장 큰 정수를 한 줄에 출력한다.

3 10
84 126 210

7

4 100
35 64 81 22

1

1 100
72

72

출처: Devin.KR 자체 제작