학원 실습 꾸러미

문제

한 학원에서는 수업이 시작되기 전에 학생들에게 나누어 줄 실습 꾸러미를 만든다. 꾸러미 하나에는 연습 카드가 정확히 K장 들어가야 한다. 카드를 더 넣거나 덜 넣은 꾸러미는 완성된 꾸러미로 세지 않는다. 학원은 이번 준비 작업에 사용할 카드를 N개의 상자에 나누어 보관하고 있다. 각 상자에는 카드가 몇 장 들어 있는지 적혀 있다. 상자에 적힌 수는 모두 정확하며, 카드의 종류나 상태에는 차이가 없다. 담당자는 모든 상자를 열어 카드를 한곳에 모은 다음 꾸러미를 만든다. 따라서 한 상자에 들어 있던 카드만으로 꾸러미를 만들 필요는 없으며, 서로 다른 상자의 카드를 자유롭게 섞어서 사용할 수 있다. 담당자는 완성된 꾸러미의 수가 가장 많아지도록 카드를 배분한다. 카드 한 장은 하나의 꾸러미에만 넣을 수 있고, 준비 작업 도중 카드를 새로 가져오거나 버리지는 않는다. 완성된 꾸러미를 더 만들 수 없을 만큼 카드가 적게 남으면 작업을 마친다. 이때 남은 카드는 다음 수업을 위해 별도로 보관하며, 미완성 꾸러미의 수를 세지는 않는다. 예를 들어 서로 다른 상자에서 꺼낸 카드들을 합쳐 하나의 꾸러미를 완성하는 것도 허용된다. 반대로 카드가 들어 있는 상자가 여러 개이더라도, 전체 카드 수가 K보다 작다면 완성할 수 있는 꾸러미는 없다. 모든 상자가 비어 있을 수도 있으며, 이 경우 완성된 꾸러미와 남은 카드의 수는 모두 0이다. 상자의 수, 꾸러미 하나에 필요한 카드 수, 각 상자의 카드 수가 주어진다. 모든 카드를 모아 만들 수 있는 완성된 꾸러미의 최대 개수와, 그만큼 만든 뒤 남는 카드의 수를 구한다. 상자의 순서는 결과에 영향을 주지 않는다.

입력

첫째 줄에 정수 N과 K가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 1,000이며 1 ≤ K ≤ 1,000이다.
둘째 줄에 각 상자의 카드 수를 나타내는 정수 A_1, A_2, ..., A_N이 공백으로 구분되어 주어진다. 모든 i에 대해 0 ≤ A_i ≤ 1,000이다.

출력

완성된 꾸러미의 최대 개수와 남는 카드의 수를 이 순서대로 공백 하나로 구분하여 한 줄에 출력한다. 완성된 꾸러미가 없으면 첫 번째 값으로 0을 출력하고, 남는 카드가 없으면 두 번째 값으로 0을 출력한다.

4 7
3 8 0 9

2 6

3 10
2 0 4

0 6

2 5
0 0

0 0

출처: Devin.KR 자체 제작