공연 안내 꾸러미의 반복 배치

문제

공연장에서는 여러 구역에 배부할 안내 꾸러미를 준비하고 있다. 꾸러미는 구역별로 구분되어 있으며, i번 구역에 보내야 하는 꾸러미는 A_i개이다. 모든 꾸러미는 반드시 배부해야 하고, 다른 구역의 꾸러미로 바꾸거나 일부를 남겨 둘 수 없다. 각 A_i는 양의 정수이다. 운영 담당자는 배부 작업을 여러 차례로 나누되, 매 차례에 정확히 같은 구성을 전달하려고 한다. 배부 차례의 수를 g라고 할 때, 각 구역에 전달하는 꾸러미의 개수가 모든 차례에서 같아야 한다. 즉, i번 구역에는 매 차례 A_i를 g로 나눈 개수의 꾸러미를 전달한다. 꾸러미 하나를 쪼갤 수 없으므로 이 개수는 반드시 정수여야 한다. 서로 다른 구역에 전달하는 개수까지 같을 필요는 없다. 예를 들어 어떤 두 구역의 준비 수량이 각각 8개와 12개라면, 네 차례에 걸쳐 매번 첫 구역에 2개, 둘째 구역에 3개를 전달할 수 있다. 반면 세 차례로 나누면 첫 구역의 수량을 같은 정수 개수로 배분할 수 없으므로 허용되지 않는다. 한 차례에 모든 꾸러미를 전달하는 방법은 언제나 허용된다. 공연 준비 시간 때문에 배부 차례의 수는 K를 넘을 수 없다. 담당자는 이 제한을 지키면서 가능한 한 많은 차례로 나누려고 한다. 선택해야 할 가장 큰 g와, 그때 한 차례에 모든 구역을 합쳐 전달하는 꾸러미의 총개수를 구한다. 최대인 g는 하나의 정수로 유일하게 결정되므로 별도의 동점 처리는 없다. 구역의 나열 순서는 결과에 영향을 주지 않으며, 입력에 같은 준비 수량이 여러 번 등장할 수도 있다.

입력

첫째 줄에 정수 N과 K가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 30,000, 1 ≤ K ≤ 1,000,000이다.
둘째 줄에 정수 A_1, A_2, ..., A_N이 공백으로 구분되어 주어진다. 모든 i에 대해 1 ≤ A_i ≤ 1,000,000이다.

출력

가능한 가장 큰 배부 차례의 수 g와, 그때 한 차례에 전달하는 꾸러미의 총개수를 공백으로 구분하여 한 줄에 출력한다. 조건을 만족하는 g는 항상 존재한다.

3 5
12 18 30

3 20

2 10
7 11

1 18

1 8
36

6 6

출처: Devin.KR 자체 제작