회의실 예약 칸의 길이

문제

한 건물의 회의실 관리자는 예약 화면에 표시할 시간 칸의 길이를 정하려 한다. 현재 화면에는 N개의 예약이 있으며, i번째 예약의 이용 시간은 A_i분이다. 모든 이용 시간은 양의 정수이고, 예약이 시작되는 실제 시각이나 어느 회의실의 예약인지는 이번 작업에 영향을 주지 않는다. 관리자는 각 예약의 이용 시간만 보고 화면을 나누려 한다. 화면 전체에서 사용하는 시간 칸의 길이는 양의 정수 d분으로 같아야 한다. 각 예약은 자기 시작 시각부터 d분짜리 칸으로 나누어 표시한다. 예약의 마지막에 d분보다 짧은 칸을 남기거나, 예약이 끝난 뒤까지 칸을 늘려 표시하는 것은 허용하지 않는다. 따라서 모든 i에 대해 A_i가 d로 나누어떨어져야 한다. 서로 다른 예약의 칸을 합쳐 하나의 칸으로 표시할 수도 없다. 또한 화면 설정에는 한 칸이 너무 길어지는 것을 막는 상한 B가 있다. 선택한 d는 B 이하여야 한다. 관리자는 이 조건들을 만족하는 d 중 가장 큰 값을 사용하려 한다. 모든 예약 시간이 정수 분이므로 d를 1로 선택하면 항상 조건을 만족한다. 따라서 사용할 수 있는 칸의 길이가 없는 경우는 발생하지 않는다. 칸의 길이를 정한 뒤에는 화면에 표시할 전체 칸 수도 계산해야 한다. i번째 예약에 필요한 칸 수는 A_i를 d로 나눈 값이며, 전체 칸 수는 모든 예약의 칸 수를 더한 값이다. 이용 시간이 같은 예약이 여러 개 있어도 각각 별도의 예약으로 계산한다. 예약이 입력된 순서는 결과에 영향을 주지 않는다. 조건을 만족하는 가장 큰 칸의 길이 d와 그 길이를 사용했을 때의 전체 칸 수를 구한다. 가장 큰 길이라는 기준으로 d가 하나로 정해지므로 별도의 동점 처리는 필요하지 않다. 전체 칸 수는 32비트 부호 있는 정수의 범위를 넘을 수 있다.

입력

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

출력

첫째 줄에 선택한 칸의 길이 d와 전체 칸 수를 공백 하나로 구분하여 출력한다.

3 8
24 36 60

6 20

4 100
7 11 13 17

1 48

1 7
36

6 6

출처: Devin.KR 자체 제작