반납 수레의 출발 규칙

문제

도서관에서는 반납된 책을 접수 순서대로 수레에 실어 서가로 보낸다. 각 책에는 목적 구역 번호와 무게가 적혀 있다. 수레 한 대에 실을 수 있는 무게의 합은 C 이하이며, 한 수레에는 목적 구역이 같은 책만 실을 수 있다. 모든 책의 무게는 C 이하이므로 책 한 권을 싣지 못하는 경우는 없다. 처음에는 빈 수레 한 대가 접수대에 있다. 직원은 다음 책을 확인하고 현재 수레에 실을 수 있으면 바로 싣는다. 현재 수레에 책이 있고, 다음 책의 목적 구역이 수레에 실린 책의 목적 구역과 다르거나 다음 책을 실었을 때 무게의 합이 C를 초과하면 현재 수레를 먼저 출발시킨다. 그 뒤 새 빈 수레에 해당 책을 싣는다. 두 조건이 동시에 성립해도 수레는 한 대만 출발한다. 수레의 무게가 정확히 C가 되었다는 이유만으로 즉시 출발시키지는 않는다. 다음 책을 확인했을 때 앞의 규칙에 따라 출발 여부를 결정한다. 모든 책을 처리한 뒤에는 책이 남아 있는 마지막 수레도 출발시킨다. 책의 순서를 바꾸거나 이미 실은 책을 다른 수레로 옮길 수 없다. 빈 수레는 출발 횟수에 포함하지 않는다. 도서관은 오늘 필요한 수레 운행 횟수와 마지막 운행의 적재량을 기록하려 한다. 마지막 운행의 적재량은 마지막으로 출발한 수레에 실린 책 무게의 합이다. 반납된 책이 한 권도 없다면 운행 횟수와 마지막 적재량을 모두 0으로 기록한다. 주어진 규칙대로 모든 책을 처리했을 때 두 기록값을 구한다.

입력

첫째 줄에 정수 N과 C가 주어진다. 0≤N≤20,000, 1≤C≤1,000,000이다. 다음 N개 줄에 접수 순서대로 정수 G와 W가 주어진다. G는 목적 구역 번호이며 1≤G≤100이다. W는 책의 무게이며 1≤W≤C이다.

출력

출발한 수레의 수와 마지막으로 출발한 수레의 적재량을 공백으로 구분하여 한 줄에 출력한다. N=0이면 0 0을 출력한다.

6 10
1 4
1 6
1 2
2 3
2 7
2 1

4 1

0 1

0 0

3 8
4 2
4 3
4 3

1 8

출처: Devin.KR 자체 제작