같은 구성의 지원 상자

문제

사내 IT 지원실에서는 여러 업무 공간에 보낼 예비 부품을 정리하고 있다. 부품은 종류별로 구분되어 있으며, 같은 종류에 속한 부품끼리는 서로 구별하지 않는다. 지원 담당자는 보관 중인 부품을 여러 상자에 나누어 담아, 어느 상자를 보내더라도 같은 구성을 제공하려 한다. 상자의 크기는 충분히 커서 담는 부품 수에는 제한이 없다. 상자를 b개 준비한다면 모든 상자에 각 종류의 부품이 똑같은 개수로 들어가야 한다. 예를 들어 한 상자에 첫 번째 종류의 부품을 3개 넣었다면, 다른 모든 상자에도 첫 번째 종류의 부품을 정확히 3개씩 넣어야 한다. 서로 다른 종류끼리 개수가 같을 필요는 없다. 한 상자에 첫 번째 종류가 3개, 두 번째 종류가 5개 들어가는 구성도 가능하다. 이번 작업에서는 보관 중인 부품을 하나도 남기지 않고 전부 사용해야 한다. 부품을 버리거나 새로 구매하거나, 한 부품을 여러 조각으로 나누는 것은 허용하지 않는다. 따라서 상자 수를 정하면 각 종류의 부품 수가 그 상자 수로 나누어떨어져야 한다. 입력에 등장하는 모든 종류에는 부품이 적어도 하나 있으므로, 가능한 분배에서는 모든 상자에 모든 종류의 부품이 들어간다. 지원실은 최소 두 공간에 부품을 보내려 하므로 상자를 2개 이상 만들어야 한다. 한편 이번에 사용할 수 있는 빈 상자는 최대 K개다. 가능한 상자 수가 여러 개라면 가장 많은 상자를 사용하는 수를 선택한다. 상자 수가 같을 때는 각 종류를 상자마다 담는 개수가 자동으로 정해지므로 별도의 동점 처리는 필요하지 않다. 종류별 부품 수와 사용할 수 있는 상자 수의 상한이 주어졌을 때, 조건을 만족하는 가장 큰 상자 수를 구한다. 빈 상자를 남기는 것은 허용하지만 부품을 남기는 것은 허용하지 않는다. 2개 이상 K개 이하의 상자로 조건을 만족시킬 수 없다면 0을 출력한다.

입력

첫째 줄에 부품 종류 수 N과 상자 수의 상한 K가 공백으로 주어진다. N과 K는 정수이며 1≤N≤30,000, 1≤K≤100,000이다.
둘째 줄에 종류별 부품 수 A₁, A₂, …, Aₙ이 공백으로 주어진다. 모든 Aᵢ는 정수이며 1≤Aᵢ≤100,000이다.

출력

조건을 만족하는 가장 큰 상자 수를 정수 하나로 출력한다. 가능한 상자 수가 없으면 0을 출력한다.

3 8
36 60 84

6

2 10
14 25

0

1 1
100

0

출처: Devin.KR 자체 제작