사탕 포장

사탕을 싫어하는 사람은 없다. 사탕은 경쟁 프로그래밍 실력까지 높여 준다! 그래서 할머니에게서 사탕 공장을 물려받은 당신은 매우 운이 좋았다. 공짜 사탕이 나오는 덕분에 ProgrammingWeights 플랫폼에서 레이팅이 최소 42 이상 오르기를 바란다. 물론 공장을 성공적으로 운영해 돈도 벌고 싶다.

사탕 공장 운영은 생각보다 간단하지 않다. 공장을 인수한 뒤 가장 먼저 한 일은 컴퓨터 과학 연구를 바탕으로 시장 조사를 하는 것이었다. 구체적으로는 사탕의 인지도를 최대한 넓히기 위해 서로 다른 종류의 사탕을 상자에 어떻게 최적으로 담을지 알아보는 것이다.

신중한 시장 조사로 두 가지 규칙이 나왔다.

• 우선, 한 종류의 사탕만 담은 상자를 파는 것은 매우 나쁘다. 그 사탕을 싫어하는 사람에게 팔리면 그 사람은 화를 낼 것이다.
• 다음으로, 어떤 종류의 사탕을 모두 한 상자에 넣는 것도 나쁘다. 상자를 산 사람이 그 종류를 좋아하더라도 추가로 살 이유가 없어지기 때문이다. 이 제한은 해당 종류의 사탕이 하나뿐인 경우에는 적용되지 않는다.

현재 $1$부터 $M$까지 번호가 매겨진 $M$개 종류의 사탕이 있다. 사탕은 크기가 $K$인 상자에 담아야 한다. 위 마케팅 규칙 외에도, 상자에는 정확히 $K$개의 사탕이 들어가야 한다.

이 규칙들 때문에 모든 사탕을 담는 것이 불가능할 수도 있다. 예를 들어 한 종류의 사탕만 있다면 상자를 하나도 만들 수 없다. 또 상자 크기가 2인데 사탕 개수가 홀수라면, 적어도 한 개는 남는다. 남은 사탕은 할인 가격에 팔면 되지만, 이익을 최대화하는 편이 낫다.

상황을 개선하기 위해, 사탕 하나를 골라 임의의 재료를 더하면 완전히 새로운 종류의 사탕으로 바꿀 수 있다. (새 종류는 기존 어떤 종류와도 같지 않으며, 사탕마다 서로 다른 새 종류가 된다.) 이 작업은 원하는 만큼 몇 번이든 할 수 있다. 다만 비용이 드는 과정이므로 가능한 한 적게 하고 싶다. 또한 가능한 한 많은 상자를 포장하고 싶다.

포장할 수 있는 상자의 최대 개수와, 그 개수의 상자를 포장하기 위해 수정해야 하는 사탕 개수의 최솟값을 구하라.

첫 줄에 두 정수 $M$과 $K$가 공백으로 구분되어 주어진다 ($1 \le M \le 10^5$, $2 \le K \le 10^9$).

다음 줄에는 $M$개의 정수 $a_1, \dots, a_M$ ($1 \le a_i \le 10^9$)이 주어진다. 각 값은 해당 종류의 사탕 개수이다.

포장할 수 있는 상자의 최대 개수와, 그 개수의 상자를 포장하기 위해 수정해야 하는 사탕 개수의 최솟값을 공백으로 구분해 출력한다.