캠핑장의 장비 세척 물통

문제

캠핑장 관리소는 퇴실 시간에 맞추어 공용 장비를 세척한다. 오늘 세척을 요청한 팀은 N팀이며, 각 팀은 빌린 장비를 하나의 묶음으로 맡겼다. 관리소가 사용할 수 있는 세척용 물은 모두 W리터다. 각 묶음을 완전히 세척하는 데 필요한 물의 양은 장비 종류와 사용 상태에 따라 다르며, 모두 양의 정수 리터로 주어진다. 장비 묶음 하나를 세척하기로 했다면 그 묶음에 필요한 물을 전부 사용해야 한다. 물을 일부만 사용하여 부분적으로 세척하는 것은 허용하지 않는다. 묶음을 나누거나 다른 팀의 묶음과 합칠 수도 없다. 각 묶음은 최대 한 번만 세척할 수 있으며, 세척하지 않은 묶음에는 물을 사용하지 않는다. 서로 다른 묶음을 세척할 때 필요한 물의 양은 단순히 더해진다. 함께 세척해서 물이 절약되거나, 앞서 쓴 물을 다시 사용하는 일은 없다. 관리소의 첫 번째 목표는 완전히 세척한 묶음의 수를 최대한 늘리는 것이다. 사용할 물의 합이 W를 넘으면 안 되며, 정확히 W리터를 사용하는 것은 허용한다. 최대 개수의 묶음을 세척하는 방법이 여러 개라면, 그중 사용한 물의 합이 가장 작은 방법을 택한다. 따라서 같은 수의 팀을 처리할 수 있다면 물을 더 많이 남기는 쪽을 선택한다. 필요한 물의 양이 같은 묶음이 여러 개 있어도 각각 별개의 묶음으로 센다. 어떤 팀의 묶음을 선택했는지는 출력하지 않으므로, 선택한 팀까지 정하는 별도의 동점 규칙은 없다. 어느 묶음도 세척할 수 없다면 세척한 묶음의 수는 0이고, 남은 물은 처음의 W리터다. W가 0인 경우도 입력으로 주어질 수 있다. 최대한 많은 묶음을 세척하면서 위 규칙을 지켰을 때, 세척한 묶음의 수와 남은 물의 양을 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N과 W가 주어진다. 1≤N≤50,000, 0≤W≤1,000,000,000이다.
둘째 줄에 각 묶음을 완전히 세척하는 데 필요한 물의 양 A_1, …, A_N이 공백으로 구분되어 주어진다. 모든 값은 정수이며 1≤A_i≤999이다.

출력

최대로 세척할 수 있는 묶음의 수와, 그 개수를 세척하는 방법 중 물을 가장 적게 사용했을 때 남은 물의 양을 공백으로 구분하여 한 줄에 출력한다.

5 13
8 3 6 2 3

3 5

4 0
1 1 2 3

0 0

4 20
5 5 4 2

4 4

출처: Devin.KR 자체 제작