농장의 공통 묶음 규격

문제

한 농장에서는 여러 구역에서 수확한 줄기 작물을 구역별로 보관하고 있다. 출하 담당자는 작물을 일정한 수의 줄기씩 묶어 판매하려 한다. 작업자가 구역을 옮길 때마다 묶음 규격을 다시 확인하는 일을 줄이기 위해, 이번 출하에서는 모든 구역에 같은 묶음 규격을 사용하기로 했다. 묶음 규격 x는 묶음 하나에 들어가는 줄기의 수를 뜻하는 양의 정수다. 각 구역에서 수확한 작물은 그 구역 안에서만 묶어야 하며, 서로 다른 구역의 줄기를 섞어 하나의 묶음을 만들 수 없다. 수확한 줄기는 하나도 남기거나 버릴 수 없고, 모든 묶음에는 정확히 x개의 줄기가 들어가야 한다. 따라서 어느 한 구역이라도 수확량을 x로 나누었을 때 나머지가 생기면 그 규격은 사용할 수 없다. 출하 장비에는 묶음 하나에 넣을 수 있는 줄기 수의 상한 K가 있다. 담당자는 이 상한을 넘지 않는 사용 가능한 규격 중에서 가장 큰 x를 선택한다. 묶음이 클수록 포장 작업의 횟수가 줄어들기 때문이다. 선택한 규격으로 각 구역을 모두 포장한 뒤에는 구역별로 만들어진 묶음 수를 더하여 전체 묶음 수를 기록한다. 구역의 수확량이 같아도 서로 다른 구역이라면 각각 포장하고 각각의 묶음 수를 더한다. 모든 구역의 수확량은 양수이며 K도 양수다. 따라서 한 줄기씩 묶는 규격은 언제나 사용할 수 있으므로 답이 없는 경우는 발생하지 않는다. 가장 큰 규격이라는 조건으로 선택된 x는 하나로 정해지며 별도의 동점 처리는 필요하지 않다. 구역별 수확량과 장비의 상한이 주어졌을 때, 선택할 묶음 규격과 전체 묶음 수를 구하는 프로그램을 작성하라.

입력

첫째 줄에 구역 수 N과 장비의 상한 K가 공백으로 주어진다. N과 K는 정수이며 1≤N≤30,000, 1≤K≤1,000,000이다. 둘째 줄에 각 구역의 수확량 A₁, A₂, …, A_N이 공백으로 주어진다. 각 A_i는 1 이상 1,000,000 이하의 정수다.

출력

선택할 묶음 규격 x와 전체 묶음 수를 한 줄에 공백으로 구분하여 출력한다. 전체 묶음 수는 32비트 부호 있는 정수의 범위를 넘을 수 있다.

3 8
36 60 84

6 30

2 20
14 25

1 39

1 7
30

6 5

출처: Devin.KR 자체 제작