공연장 미리 듣기 좌석

문제

한 공연장은 본공연에 앞서 짧은 미리 듣기 행사를 연다. 행사에 사용할 수 있는 좌석은 S개이며, 사전에 신청한 관람 모임은 N개이다. 모임에는 신청 순서대로 1번부터 N번까지 번호가 붙어 있다. 각 모임은 함께 입장할 인원수를 제출했다. 운영자는 가능한 한 많은 모임에 미리 듣기 기회를 주려 한다. 한 모임을 초대하면 그 모임의 신청 인원 전원에게 좌석을 제공해야 한다. 일부 인원만 초대하거나 한 모임을 여러 모임으로 나누는 것은 허용되지 않는다. 서로 다른 모임의 인원은 각각 따로 계산하며, 같은 인원수로 신청했더라도 별개의 모임이다. 이번 행사는 좌석 위치를 지정하지 않고 입장한 사람이 빈자리에 앉는 방식이다. 따라서 같은 모임이 연속된 자리에 앉을 필요는 없으며, 초대한 모임들의 인원수 합이 S 이하이면 모두 입장할 수 있다. 좌석을 남겨도 되고, 모든 좌석을 반드시 채울 필요는 없다. 한 모임의 신청 인원수가 S보다 클 수도 있으며, 그러한 모임은 초대할 수 없다. 초대할 수 있는 모임 수의 최댓값을 구한다. 그 최댓값을 달성하는 선택이 여러 개라면 그중 전체 인원수가 가장 작은 선택을 사용한다. 모임 수와 전체 인원수까지 같은 선택이 여러 개라면 선택한 모임 번호를 오름차순으로 나열했을 때 사전순으로 가장 앞서는 목록을 사용한다. 같은 길이의 두 목록은 처음으로 값이 다른 위치에서 번호가 더 작은 목록이 사전순으로 앞선다. 결과를 전달할 때에는 선택한 모임을 신청 순서대로 안내한다. 따라서 최종 목록은 선택 과정의 순서와 관계없이 모임 번호의 오름차순으로 출력한다. 한 모임도 초대할 수 없다면 모임 수와 전체 인원수는 모두 0이며, 목록 대신 -1을 출력한다.

입력

첫째 줄에 신청 모임 수 N과 사용 가능한 좌석 수 S가 공백으로 주어진다. 1 ≤ N ≤ 20,000, 1 ≤ S ≤ 1,000,000,000이다.
둘째 줄에 1번부터 N번 모임까지의 신청 인원수 A_i가 공백으로 주어진다. 1 ≤ A_i ≤ 1,000,000이다.
입력에 등장하는 모든 수는 정수이다.

출력

첫째 줄에 선택한 모임 수와 전체 인원수를 공백으로 구분하여 출력한다. 둘째 줄에는 선택한 모임 번호를 오름차순으로 공백으로 구분하여 출력한다. 선택한 모임이 없으면 둘째 줄에 -1을 출력한다.

5 10
4 2 5 2 3

3 7
2 4 5

4 5
2 2 2 4

2 4
1 2

3 2
3 5 4

0 0
-1

출처: Devin.KR 자체 제작