주차장 점검 순서

문제

주차장 관리실은 운영을 시작하기 전에 주차 구역의 안내 장치를 점검한다. 오늘 점검 후보에 오른 장치는 N개이며, 각 장치를 점검하는 데 필요한 시간이 미리 정해져 있다. 관리자는 운영 시작까지 남은 T분 동안 가능한 한 많은 장치의 점검을 끝내려고 한다. 점검 담당자는 한 명이므로 두 장치를 동시에 점검할 수 없다. 한 장치의 점검을 시작하면 정해진 시간 동안 계속 진행해야 하며, 중간에 멈춘 장치는 점검을 끝낸 것으로 인정하지 않는다. 점검할 장치와 점검 순서는 자유롭게 정할 수 있다. 장치 사이를 이동하거나 다음 점검을 준비하는 시간은 따로 들지 않는다. 따라서 선택한 장치들의 점검 시간 합이 T 이하이면 그 장치들을 모두 점검할 수 있다. 관리실은 결과를 두 수로 기록한다. 첫 번째 수는 제한 시간 안에 점검을 끝낼 수 있는 장치 수의 최댓값이다. 두 번째 수는 그 최대 개수를 달성하는 선택들 가운데 점검 시간 합의 최솟값이다. 같은 개수의 장치를 점검할 수 있다면 시간을 적게 쓰는 선택을 기록해야 한다. 두 값이 모두 같은 선택이 여러 개여도 어떤 장치를 골랐는지는 출력하지 않는다. 각 점검 시간은 양의 정수이므로 시간이 전혀 남아 있지 않으면 어떤 장치도 점검할 수 없다. 시간이 남아 있더라도 모든 장치의 점검 시간이 T보다 크다면 결과는 같다. 이처럼 하나도 점검할 수 없는 경우 두 기록값은 모두 0이다. 주어진 시간 정보를 바탕으로 관리실에 남길 두 기록값을 구한다.

입력

첫째 줄에 정수 N과 T가 공백으로 주어진다. 1 ≤ N ≤ 100,000, 0 ≤ T ≤ 1,000,000,000이다.
둘째 줄에 각 장치의 점검 시간인 정수 a_1, a_2, ..., a_N이 공백으로 주어진다. 1 ≤ a_i ≤ 999이며 단위는 분이다.

출력

점검을 끝낼 수 있는 장치 수의 최댓값과, 그 개수를 달성하는 점검 시간 합의 최솟값을 공백으로 구분하여 출력한다. 하나도 점검할 수 없으면 0 0을 출력한다.

5 12
6 3 8 2 4

3 9

4 0
1 1 2 3

0 0

4 20
5 5 5 5

4 20

출처: Devin.KR 자체 제작