호텔 객실의 점검 예산

문제

한 호텔은 손님을 받기 전에 비어 있는 객실 가운데 일부를 골라 추가 점검을 하려 한다. 객실마다 필요한 작업이 달라 점검 비용도 서로 다르다. 시설 담당자는 객실별 점검 비용과 이번에 사용할 수 있는 전체 예산을 전달받았다. 점검을 선택한 객실의 비용을 모두 더한 값은 예산을 넘을 수 없다. 객실 하나의 점검을 여러 번 나누어 선택할 수는 없다. 어떤 객실을 점검하려면 그 객실의 비용을 전부 지불해야 하며, 같은 객실은 한 번만 선택할 수 있다. 반대로 비용이 같은 서로 다른 객실은 각각 선택할 수 있다. 객실 사이에는 작업상의 의존 관계가 없으므로 어느 객실을 고르더라도 다른 객실의 비용은 바뀌지 않는다. 모든 객실은 추가 점검 대상으로서 같은 가치를 가진다. 시설 담당자의 첫 번째 목표는 예산 안에서 점검하는 객실 수를 최대한 늘리는 것이다. 최대 객실 수를 달성하는 선택이 여러 가지라면, 그중 지출하는 총비용이 가장 작은 선택을 사용한다. 비용이 같은 선택까지 구별할 필요는 없다. 선택한 객실의 번호나 점검 순서는 출력하지 않고, 최대로 점검할 수 있는 객실 수와 그 수를 달성하는 최소 총비용만 출력한다. 예산을 모두 사용할 필요는 없다. 예산이 남더라도 추가로 선택할 수 있는 객실이 없으면 점검을 마친다. 모든 객실의 점검이 가능하면 객실을 전부 선택한다. 예산이 0이거나 어떤 객실의 비용도 지불할 수 없다면 아무 객실도 선택하지 않으며, 이때 객실 수와 총비용은 모두 0이다. 주어진 비용 목록을 이용하여 담당자가 보고할 두 값을 구하는 프로그램을 작성한다.

입력

첫째 줄에 객실 수 N과 예산 B가 공백으로 구분되어 주어진다. N은 1 이상 100,000 이하의 정수이고 B는 0 이상 9,900,000 이하의 정수다.
둘째 줄에 각 객실의 점검 비용 A_1, A_2, ..., A_N이 공백으로 구분되어 주어진다. 각 비용은 1 이상 99 이하의 정수다. 같은 비용이 여러 번 나타날 수 있다.

출력

최대로 점검할 수 있는 객실 수와, 그 수의 객실을 점검하는 데 필요한 최소 총비용을 공백으로 구분하여 한 줄에 출력한다. 아무 객실도 선택할 수 없으면 0 0을 출력한다.

5 14
8 3 3 6 2

4 14

4 1
2 5 2 9

0 0

3 20
4 4 4

3 12

출처: Devin.KR 자체 제작