편의점 작은 진열대

문제

한 편의점은 계산대 옆의 작은 진열대에서 같은 종류의 상품만 판매한다. 진열대에는 상품을 최대 K개까지 놓을 수 있다. 영업 기록을 처리하기 직전에는 상품이 S개 놓여 있다. 직원은 이후에 발생한 입고와 구매 요청을 기록된 순서대로 처리하려고 한다. 입고 기록에는 진열대에 새로 놓으려는 상품 수가 적혀 있다. 직원은 진열대의 빈자리만큼 상품을 놓는다. 입고된 상품이 빈자리보다 많으면 빈자리를 모두 채우고 나머지는 반송한다. 반송한 상품은 이후 기록에서 사용할 수 없으며, 편의점 안의 다른 장소에 보관하지도 않는다. 진열대가 이미 가득 차 있다면 해당 입고 상품을 전부 반송한다. 구매 요청 기록에는 손님이 사고 싶은 상품 수가 적혀 있다. 진열대의 상품이 충분하면 요청한 수만큼 판매한다. 상품이 부족하면 현재 진열대에 있는 상품을 모두 판매한다. 손님은 실제로 받은 수량만 구매하며, 받지 못한 수량을 나중에 다시 받거나 다음 손님의 상품보다 먼저 배정받지 않는다. 진열대가 비어 있다면 그 요청으로 판매되는 상품은 0개이다. 각 기록의 처리는 다음 기록이 시작되기 전에 끝난다. 따라서 뒤에 들어온 상품으로 앞선 구매 요청을 처리할 수 없다. 같은 종류의 기록이 연속으로 나타나더라도 하나씩 순서대로 처리하며, 기록을 합치거나 순서를 바꾸지 않는다. 상품의 가격이나 손님의 수는 계산하지 않는다. 모든 기록을 처리한 뒤 진열대에 남은 상품 수, 실제로 판매한 상품의 총수, 입고 과정에서 반송한 상품의 총수를 구한다. 초기 상품 S개는 입고 기록에 포함되지 않으며 반송 수에도 포함되지 않는다. 판매 요청 수의 합이 아니라 실제로 손님에게 건넨 수량의 합을 계산해야 한다. 판매나 반송이 한 번도 일어나지 않았다면 해당 총수는 0이다.

입력

첫째 줄에 기록 수 N, 진열대의 최대 수량 K, 초기 상품 수 S가 공백으로 구분되어 주어진다. 모두 정수이며 1 ≤ N ≤ 1,000, 1 ≤ K ≤ 1,000, 0 ≤ S ≤ K이다.
다음 N개 줄에는 기록의 종류 t와 수량 q가 공백으로 구분되어 주어진다. t와 q는 정수이며 t는 1 또는 2이고 1 ≤ q ≤ 1,000이다. t가 1이면 q개를 입고하려는 기록이고, t가 2이면 q개를 구매하려는 요청이다.

출력

모든 기록을 처리한 뒤 남은 상품 수, 실제 판매한 상품의 총수, 반송한 상품의 총수를 이 순서대로 공백으로 구분하여 한 줄에 출력한다.

5 10 3
1 9
2 4
2 8
1 5
2 2

3 12 2

3 1 0
2 5
1 3
1 2

1 0 4

2 5 5
2 2
2 3

0 5 0

출처: Devin.KR 자체 제작