공연장 좌석 묶음 규격

문제

한 공연장은 다음 공연의 좌석 안내표를 새로 만들고 있다. 공연장에는 서로 구분되는 N개의 좌석 구역이 있으며, 각 구역에는 사용할 수 있는 좌석이 양의 정수 개만큼 있다. 안내표에는 좌석 하나마다 표시를 붙이는 대신, 일정한 수의 좌석을 하나의 묶음으로 표시하려 한다. 이 작업에서 묶음은 좌석 개수를 나누는 단위이며 실제 좌석의 위치나 배치는 고려하지 않는다. 운영자는 모든 구역에 같은 묶음 크기 k를 적용해야 한다. 한 묶음에 들어가는 좌석 수는 정확히 k개이며, 하나의 묶음이 서로 다른 구역의 좌석을 함께 포함할 수는 없다. 또한 어느 구역에서도 좌석을 남기거나 안내표에서 제외할 수 없다. 따라서 모든 구역의 좌석을 각각 크기 k인 묶음으로 정확히 나눌 수 있어야 해당 크기를 사용할 수 있다. 좌석 하나만을 묶음으로 표시하는 방식은 이번 안내표의 목적에 맞지 않으므로 k는 2 이상이어야 한다. 인쇄 장치의 설정 때문에 k는 입력으로 주어지는 상한 K 이하여야 한다. 조건을 만족하는 서로 다른 정수 k는 각각 하나의 규격으로 센다. 같은 규격을 적용했을 때 구역마다 생기는 묶음 수가 달라도 상관없으며, 묶음 수 자체를 답으로 출력하지는 않는다. 운영자는 사용할 수 있는 규격이 몇 개인지 먼저 확인한 뒤, 그중 가장 큰 규격으로 시험 안내표를 만들 계획이다. 모든 구역의 좌석 수와 상한을 읽고 가능한 규격의 개수와 가장 큰 규격을 구한다. 사용할 수 있는 규격이 하나도 없다면 두 값 모두 0으로 보고한다. 규격은 크기인 정수 값으로 구별하므로 가장 큰 규격에 대한 동점 처리는 필요하지 않다.

입력

첫째 줄에 구역 수 N과 묶음 크기의 상한 K가 주어진다. N과 K는 정수이며 1 ≤ N ≤ 30,000, 1 ≤ K ≤ 1,000,000,000이다.
둘째 줄에 각 구역의 좌석 수 A1, A2, ..., AN이 공백으로 구분되어 주어진다. 모든 Ai는 정수이며 1 ≤ Ai ≤ 1,000,000,000이다.

출력

조건을 만족하는 서로 다른 묶음 크기의 개수와 그중 가장 큰 크기를 공백으로 구분하여 한 줄에 출력한다. 가능한 크기가 없으면 0 0을 출력한다.

3 8
24 36 60

4 6

3 100
14 25 39

0 0

1 9
36

5 9

출처: Devin.KR 자체 제작