캠핑장 상자에 맞는 묶음

문제

한 캠핑장은 대여용 고정 핀을 보관하는 상자 N개를 관리한다. 상자는 1번부터 N번까지 번호가 붙어 있으며, i번 상자에는 고정 핀이 A_i개 들어 있다. 관리자는 다음 예약에 대비하여 각 상자의 핀을 같은 크기의 묶음으로 나누려 한다. 묶음 하나에 들어가는 핀의 개수를 양의 정수 d로 정하면, 모든 상자에서 정확히 d개씩 꺼내 묶음을 만든다. 상자마다 핀의 종류가 다르므로 서로 다른 상자의 핀을 섞을 수 없다. 핀을 다른 상자로 옮기거나, 일부를 버리거나, 새 핀을 추가하는 것도 허용하지 않는다. 따라서 모든 상자에서 묶음을 만든 뒤 남는 핀이 하나도 없어야 한다. 예를 들어 핀이 18개인 상자는 d가 6이면 세 묶음으로 나눌 수 있지만, d가 4이면 핀 두 개가 남으므로 그 크기를 사용할 수 없다. 관리자가 사용하는 포장 도구는 한 묶음에 핀을 최대 K개까지만 넣을 수 있다. 그러므로 선택하는 d는 1 이상 K 이하인 정수여야 한다. 이 제한은 상자마다 따로 적용하는 값이 아니라 캠핑장 전체에서 사용하는 하나의 묶음 크기에 대한 제한이다. 각 상자에서 만들어지는 묶음의 개수는 서로 달라도 되며, 전체 묶음 개수를 맞출 필요는 없다. 관리자는 포장 횟수를 줄이기 위해 조건을 만족하는 d 중 가장 큰 값을 선택한다. 상자가 하나뿐인 경우에도 같은 규칙을 적용하며, K가 상자의 핀 개수보다 크더라도 핀이 없는 묶음을 만들 수는 없다. 모든 A_i가 양의 정수이므로 d를 1로 정하는 방법은 항상 가능하다. 따라서 답이 없는 입력은 주어지지 않으며, 가장 큰 묶음 크기는 하나로 정해진다. 상자에 들어 있는 핀의 개수와 포장 도구의 제한이 주어질 때, 관리자가 선택할 묶음 크기를 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N과 K가 공백으로 주어진다. 둘째 줄에 정수 A_1, A_2, …, A_N이 공백으로 주어진다.
1 ≤ N ≤ 20,000, 1 ≤ K ≤ 100,000, 1 ≤ A_i ≤ 100,000이다.

출력

모든 A_i를 나누어떨어지게 하는 1 이상 K 이하의 정수 중 가장 큰 값을 출력한다.

3 5
24 36 60

4

2 1
7 11

1

1 100
72

72

출처: Devin.KR 자체 제작