점검 전 요청 묶음

문제

게임 서버가 정기 점검을 시작하기 전에 대기 중인 요청 묶음을 처리하려 한다. 요청 묶음은 모두 같은 시점에 대기열에 들어와 있으며, 각 묶음을 처리하는 데 필요한 작업량이 정해져 있다. 서버는 점검 전까지 사용할 수 있는 작업량을 B만큼 확보했다. 운영자는 이 한도 안에서 처리를 완료하는 요청 묶음의 개수를 최대화하려 한다. 각 요청 묶음은 하나의 단위로 취급한다. 어떤 묶음을 선택했다면 그 묶음의 작업량 전체를 사용해야 하며, 일부만 처리하고 완료한 것으로 셀 수 없다. 선택하지 않은 묶음은 다음 점검 이후로 미룬다. 모든 묶음의 중요도는 같으므로 작업량이 큰 묶음을 완료하더라도 완료 개수에는 하나만 더한다. 서로 작업량이 같은 묶음도 각각 별개의 묶음이다. 서버는 선택한 묶음을 원하는 순서로 처리할 수 있다. 묶음을 처리하기 위한 준비 작업이나 묶음 사이의 전환에는 추가 작업량이 들지 않는다. 따라서 선택한 묶음들의 작업량 합이 B 이하이면 그 선택은 실행할 수 있다. 작업량 합이 B와 정확히 같은 선택도 허용된다. 대기열에 기록된 입력 순서는 선택 가능 여부나 처리 비용에 영향을 주지 않는다. 예산을 반드시 모두 사용할 필요는 없다. 모든 묶음의 작업량이 B보다 크거나 B가 0이라면 아무 묶음도 완료하지 못할 수 있다. 반대로 전체 작업량의 합이 B 이하이면 모든 묶음을 완료할 수 있다. 가능한 선택이 여러 가지라면 어떤 묶음을 선택했는지는 구분하지 않으며, 완료할 수 있는 최대 개수만 구한다. 요청 묶음의 수와 각 작업량, 사용 가능한 총작업량이 주어졌을 때 이 최대 개수를 출력하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N과 B가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 200,000, 0 ≤ B ≤ 10^12이다.
둘째 줄에 각 요청 묶음의 작업량을 나타내는 정수 A_1, A_2, ..., A_N이 공백으로 구분되어 주어진다. 1 ≤ A_i ≤ 10^9이다.

출력

완료할 수 있는 요청 묶음의 최대 개수를 정수 하나로 출력한다. 하나도 완료할 수 없으면 0을 출력한다.

6 14
8 3 5 2 7 4

4

4 0
1 1 2 3

0

3 9
3 3 3

3

출처: Devin.KR 자체 제작