회의실 비품 요청 접수

문제

회의실 운영 서버는 여러 회의실에서 보내온 비품 꾸러미 요청을 접수한다. 비품 꾸러미에는 회의에 필요한 물품이 한 세트씩 들어 있으며, 모든 꾸러미는 서로 같은 것으로 취급한다. 오늘 사용할 수 있는 꾸러미는 처음에 S개이다. 서버에는 요청 N개가 도착해 있으며, 각 요청에는 필요한 꾸러미 수가 양의 정수로 적혀 있다. 서버는 입력에 주어진 순서대로 요청을 하나씩 처리한다. 현재 남아 있는 꾸러미 수가 요청 수량 이상이면 그 요청을 승인한다. 승인한 요청에는 요구한 수량을 전부 배정하고, 배정한 수량만큼 남은 꾸러미 수를 줄인다. 현재 수량과 요청 수량이 정확히 같은 경우에도 승인하며, 처리 직후 남은 수량은 0개가 된다. 현재 남아 있는 꾸러미 수가 요청 수량보다 적으면 그 요청을 거절한다. 일부 수량만 배정하는 것은 허용되지 않는다. 거절한 요청에는 꾸러미를 하나도 배정하지 않으며, 남은 꾸러미 수는 바뀌지 않는다. 거절된 요청은 대기 목록에 넣거나 나중에 다시 처리하지 않는다. 한 요청이 거절되더라도 뒤의 요청은 계속 처리한다. 뒤에 도착한 요청의 수량이 더 작으면 앞선 요청이 거절되었어도 승인될 수 있다. 요청을 수량순으로 정렬하거나, 승인 건수를 늘리기 위해 처리 순서를 바꾸어서는 안 된다. 같은 수량의 요청이 여러 번 나타나면 각각 별개의 요청으로 처리한다. 요청을 처리하는 동안 새 꾸러미가 입고되거나 배정된 꾸러미가 반환되는 일은 없다. 처음 수량이 0개일 수도 있으며, 이 경우 모든 요청은 거절된다. 모든 요청을 순서대로 처리한 뒤 승인한 요청 수, 거절한 요청 수, 남아 있는 꾸러미 수를 구하는 프로그램을 작성한다. 승인 또는 거절한 요청이 하나도 없다면 해당 건수는 0으로 출력한다.

입력

첫째 줄에 요청 수 N과 처음 꾸러미 수 S가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 1,000, 0 ≤ S ≤ 1,000이다. 둘째 줄에 각 요청의 수량을 나타내는 정수 A_1, A_2, ..., A_N이 처리 순서대로 주어진다. 모든 i에 대해 1 ≤ A_i ≤ 1,000이다.

출력

승인한 요청 수, 거절한 요청 수, 모든 처리 후 남은 꾸러미 수를 공백으로 구분하여 한 줄에 출력한다.

5 9
6 5 2 1 1

3 2 0

3 0
1 2 1

0 3 0

4 20
3 3 3 3

4 0 8

출처: Devin.KR 자체 제작