공용 묶음 상자의 규격

문제

택배 작업장에서 여러 배송 구역으로 보낼 물품을 정리하고 있다. 각 구역으로 보내는 물품은 종류와 크기가 같으며, 구역마다 보내야 하는 물품의 개수가 정해져 있다. 서로 다른 구역의 물품을 섞어서 포장할 수는 없다. 작업장은 공용 묶음 상자의 규격을 하나 정하려고 한다. 규격이 양의 정수 d라는 것은 상자 하나에 물품을 정확히 d개씩 담는다는 뜻이다. 어떤 구역의 물품 개수가 d로 나누어떨어지면, 그 구역에서는 모든 물품을 공용 묶음 상자에 남김없이 담을 수 있다. 상자를 여러 개 사용하는 것은 허용되지만, 물품을 남기거나 일부 상자를 덜 채우는 것은 허용되지 않는다. 공용 묶음 상자를 모든 구역에서 사용할 필요는 없다. 전체 N개 구역 중 적어도 K개 구역에서 사용할 수 있으면 해당 규격을 채택할 수 있다. 나머지 구역은 별도의 방식으로 포장하므로 판단에 영향을 주지 않는다. 물품 개수가 같은 구역도 서로 다른 구역으로 세며, 한 구역은 사용할 상자의 개수와 관계없이 한 번만 센다. 작업장은 채택할 수 있는 규격 중 상자 하나에 담는 물품 개수가 가장 큰 규격을 원한다. 예를 들어 물품이 12개인 구역은 규격 3을 사용할 수 있지만, 물품이 14개인 구역은 규격 3을 사용할 수 없다. 규격 1은 모든 구역에서 사용할 수 있으므로 채택할 수 있는 규격은 항상 존재한다. 주어진 구역별 물품 개수와 K를 이용하여 가장 큰 규격을 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N과 K가 공백으로 구분되어 주어진다. 1 ≤ K ≤ N ≤ 60,000이다.
둘째 줄에 각 구역의 물품 개수를 나타내는 정수 A_1, A_2, …, A_N이 공백으로 구분되어 주어진다. 모든 i에 대해 1 ≤ A_i ≤ 60,000이다.

출력

적어도 K개 구역에서 사용할 수 있는 가장 큰 규격 d를 정수 하나로 출력한다.

5 3
18 30 42 25 7

6

4 4
8 15 21 10

1

3 1
14 9 28

28

출처: Devin.KR 자체 제작