급식 운반통의 공통 용량

문제

학교 급식실은 각 반에 보낼 음식을 운반통에 나누어 담는다. 오늘 음식을 받아야 하는 반은 N개이며, i번 반에 보내야 하는 음식의 양은 A_i인분이다. 모든 A_i는 양의 정수다. 급식실은 크기가 같은 운반통을 사용하려 하며, 운반통 하나에 담을 수 있는 최대 인분 수를 양의 정수 X로 정해야 한다. 운반통에는 반드시 한 반의 음식만 담는다. 서로 다른 반의 음식을 한 통에 섞을 수 없고, 한 반의 음식은 여러 통으로 나눌 수 있다. 각 통에는 1인분 이상 X인분 이하의 정수량을 담는다. 반마다 요청한 양을 정확히 보내야 하므로 음식을 버리거나 더 보내는 것은 허용되지 않는다. 마지막 통을 가득 채울 필요는 없으며, 비어 있는 통은 사용한 통 수에 포함하지 않는다. 급식실이 이번 배식에 사용할 수 있는 운반통은 최대 K개다. 여러 반이 같은 통을 시간차를 두고 다시 사용하는 일은 없으며, 음식을 담은 모든 통은 한 번에 반으로 출발한다. 따라서 모든 반에 필요한 운반통 수를 합한 값이 K 이하여야 한다. 사용할 수 있는 통을 전부 쓸 필요는 없다. 예를 들어 어떤 반에 8인분을 보내고 공통 용량을 3인분으로 정했다면, 그 반에는 적어도 세 통이 필요하다. 두 통에 각각 3인분, 나머지 한 통에 2인분을 담는 방법이 있다. 다른 반에도 같은 용량 제한을 독립적으로 적용한다. 급식실은 보관 공간을 줄이기 위해 조건을 만족하는 X 중 가장 작은 값을 선택하려 한다. X가 커지면 같은 음식을 더 적거나 같은 수의 통에 담을 수 있지만, 반이 다르면 음식을 합칠 수 없다는 규칙은 계속 적용된다. 주어진 최대 통 수로 모든 반의 음식을 보낼 수 있는 최소 공통 용량을 구한다. 어떤 양의 정수 X를 선택해도 불가능하다면 -1을 출력한다.

입력

첫 줄에 정수 N과 K가 주어진다. N은 1 이상 30,000 이하이며, K는 0 이상 1,000,000,000 이하다.
둘째 줄에 정수 A_1, A_2, …, A_N이 공백으로 구분되어 주어진다. 각 A_i는 1 이상 100,000,000 이하다.

출력

조건을 만족하는 최소 양의 정수 X를 출력한다. 가능한 X가 없으면 -1을 출력한다.

3 6
8 5 9

5

3 2
1 4 2

-1

4 20
2 3 1 4

1

출처: Devin.KR 자체 제작