택배 상자의 공통 묶음

문제

택배 분류소에는 목적지가 서로 다른 물품 더미가 N개 있다. i번째 더미에는 물품이 A_i개 있으며, 모든 물품은 크기와 무게가 같다고 가정한다. 분류소는 물품을 작은 상자에 나누어 담은 뒤 목적지별로 발송하려 한다. 서로 다른 더미의 물품을 하나의 상자에 섞어 담는 일은 허용하지 않는다. 분류소는 작업자가 상자마다 물품 수를 다시 확인하지 않도록, 이번 작업에서 사용하는 모든 상자에 정확히 같은 수의 물품을 담기로 했다. 상자 하나에 담는 물품 수를 d라고 하면 d는 양의 정수여야 한다. 각 더미의 물품은 남김없이 포장해야 하며, 일부 물품을 다음 작업으로 미루거나 비어 있는 자리를 다른 목적지의 물품으로 채울 수 없다. 따라서 모든 i에 대해 A_i는 d로 나누어떨어져야 한다. 한편 자동 봉함기는 상자 하나에 물품을 최대 K개까지만 넣을 수 있다. 더 적게 넣는 것은 가능하지만 K개를 초과하면 사용할 수 없다. 분류소는 필요한 상자의 총개수를 줄이고자 하므로, 이러한 조건을 모두 만족하는 d 중 가장 큰 값을 선택한다. 모든 물품 수가 양의 정수이므로 d를 1로 정하면 항상 포장이 가능하다. 예를 들어 어느 더미의 물품 수가 d의 배수가 아니라면, 다른 더미를 정상적으로 포장할 수 있더라도 그 d는 선택할 수 없다. 더미의 입력 순서는 포장 가능 여부나 선택 결과에 영향을 주지 않는다. 선택한 d와 그때 필요한 상자의 총개수를 구하는 프로그램을 작성한다. 상자의 총개수는 각 더미에서 필요한 상자 수를 모두 더한 값이다.

입력

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

출력

조건을 만족하는 가장 큰 정수 d와 필요한 상자의 총개수를 공백으로 구분하여 한 줄에 출력한다. 상자의 총개수는 32비트 정수 범위를 넘을 수 있다.

3 8
24 36 60

6 20

2 1
7 11

1 18

1 20
13

13 1

출처: Devin.KR 자체 제작