마지막 칸의 조심 택배

문제

택배 분류장에서는 운반 수레에 상자를 싣고 포장 구역으로 보낸다. 상자는 컨베이어에 놓인 순서대로 한 개씩 도착하며, 작업자는 이 순서를 바꾸거나 상자를 잠시 옆에 내려놓을 수 없다. 모든 수레의 무게 한도는 C이며, 각 상자의 무게는 C 이하인 양의 정수다. 상자에는 일반 상자와 조심 상자라는 두 종류가 있다. 작업자는 처음에 빈 수레 한 대를 준비한다. 상자가 도착했을 때 현재 수레에 실린 상자의 무게 합과 도착한 상자의 무게를 더한 값이 C 이하라면 그 상자를 현재 수레에 싣는다. 합이 정확히 C인 경우도 실을 수 있다. 합이 C를 초과한다면 현재 수레를 즉시 보내고, 새 빈 수레를 준비하여 도착한 상자를 싣는다. 무게 합이 한도와 같아졌다는 이유만으로 수레를 즉시 보내지는 않는다. 조심 상자는 다른 상자와 함께 실을 수 있지만, 그 수레에 싣는 마지막 상자여야 한다. 따라서 조심 상자를 실은 수레는 남은 무게 여유와 관계없이 즉시 보낸다. 그 뒤에 상자가 더 도착하면 새 빈 수레를 준비한다. 일반 상자를 실은 뒤에는 다음 상자가 도착할 때까지 현재 수레를 그대로 둔다. 작업자는 수레에 이미 실은 상자를 꺼내거나 다른 수레로 옮길 수 없으며, 위 규칙 이외의 이유로 수레를 미리 보내지 않는다. 마지막 상자까지 처리한 뒤 상자가 남아 있는 수레가 있다면 그 수레도 보낸다. 빈 수레는 보내지 않으며 사용한 수레 수에도 포함하지 않는다. 수레 한 대의 남은 무게 여유는 C에서 그 수레에 실린 상자의 무게 합을 뺀 값이다. 상자가 한 개 이상 주어지므로 사용하는 수레는 반드시 존재한다. 도착한 모든 상자를 처리했을 때 사용한 수레 수와, 보낸 모든 수레의 남은 무게 여유를 합한 값을 구하는 프로그램을 작성하라.

입력

첫째 줄에 상자 수 N과 수레의 무게 한도 C가 공백으로 구분되어 주어진다. N과 C는 정수이며 1 ≤ N ≤ 60,000, 1 ≤ C ≤ 999다.
다음 N개의 줄에는 도착 순서대로 각 상자의 무게 W와 종류 T가 공백으로 구분되어 주어진다. W와 T는 정수이며 1 ≤ W ≤ C, T ∈ {0, 1}이다. T가 0이면 일반 상자이고, 1이면 조심 상자다.

출력

첫째 줄에 사용한 수레 수와 모든 수레의 남은 무게 여유의 합을 공백으로 구분하여 정수로 출력한다.

7 10
4 0
6 0
2 1
3 0
5 1
2 0
8 0

4 10

3 5
1 1
1 1
1 1

3 12

1 5
5 0

1 0

출처: Devin.KR 자체 제작