지원 예산으로 고르는 교체 요청

문제

한 회사의 IT 지원팀은 직원들이 제출한 주변 기기 교체 요청을 모아 처리한다. 각 요청에는 교체에 필요한 비용이 적혀 있으며, 요청 번호는 입력에 등장하는 순서대로 1번부터 N번까지 붙는다. 서로 다른 요청의 비용이 같을 수 있다. 지원팀에는 이번 회차에 사용할 수 있는 예산 B가 있고, 모든 요청을 처리하기에는 예산이 부족할 수도 있다. 지원팀은 이번 회차에 처리하는 요청 수가 최대가 되도록 요청을 선택하려 한다. 요청 하나를 처리하려면 그 요청의 비용 전부를 지불해야 한다. 비용을 나누어 지불하거나 요청의 일부만 처리하는 것은 불가능하다. 선택한 요청들의 비용 합은 예산 B 이하여야 하며, 사용하지 않은 예산을 반드시 소진할 필요는 없다. 처리할 수 있는 요청 수가 같은 선택 방법이 여러 개라면 다음 규칙으로 하나를 결정한다. 먼저 모든 요청을 비용이 작은 순서로 정렬하고, 비용이 같다면 요청 번호가 작은 순서로 정렬한다. 이렇게 만든 목록의 앞에서부터 연속한 요청들을 선택하되, 비용 합이 B를 넘지 않는 가장 긴 앞부분을 이번 회차의 처리 목록으로 삼는다. 모든 비용은 양의 정수이므로 이 규칙으로 선택한 요청 수는 가능한 최대 요청 수와 같다. 처리 목록에 들어간 요청 번호는 정렬된 목록에서의 순서를 유지하여 출력한다. 요청 번호 자체가 작은 순서로 다시 정렬하지 않는다. 선택한 비용의 합을 예산에서 뺀 값을 남은 예산이라고 한다. 가장 저렴한 요청도 처리할 수 없다면 처리 요청 수는 0이고 남은 예산은 B이다. 요청이 모두 선택되는 경우도 있다. 처리 요청 수, 남은 예산, 그리고 처리 목록을 구하는 프로그램을 작성한다.

입력

첫째 줄에 요청 수 N과 예산 B가 공백으로 구분되어 주어진다. 둘째 줄에 요청 번호 1번부터 N번까지의 비용 C_1, C_2, ..., C_N이 공백으로 구분되어 주어진다. 모든 입력은 정수이며, 1 ≤ N ≤ 30,000, 0 ≤ B ≤ 1,000,000,000, 1 ≤ C_i ≤ 10,000이다.

출력

첫째 줄에 처리 요청 수와 남은 예산을 공백으로 구분하여 출력한다. 둘째 줄에 선택한 요청 번호를 처리 목록의 순서대로 공백으로 구분하여 출력한다. 선택한 요청이 없다면 둘째 줄에는 0을 출력한다.

6 14
7 3 3 8 2 6

4 0
5 2 3 6

3 1
4 2 2

0 1
0

4 20
5 2 5 1

4 7
4 2 1 3

출처: Devin.KR 자체 제작