급수대의 종이컵

문제

마라톤 대회의 한 급수대에서는 종이컵에 물을 담아 주자에게 나누어 준다. 운영진은 주자가 도착하는 시간을 N개의 구간으로 나누어 종이컵 재고를 관리한다. 첫 번째 구간이 시작되기 전에는 급수대에 종이컵이 S개 있다. 각 구간에서는 새 종이컵이 먼저 도착하고, 그 뒤에 해당 구간의 주자들이 물을 받으러 온다. i번째 구간이 시작되면 종이컵 A_i개가 재고에 추가된다. 이어서 주자 B_i명이 차례로 도착한다. 각 주자는 종이컵 하나에 담긴 물을 한 번만 받으려고 한다. 종이컵이 남아 있으면 주자 한 명에게 종이컵 하나를 사용한다. 종이컵을 모두 사용한 뒤에 도착한 주자는 이 급수대에서 물을 받지 못하고 그대로 지나간다. 물을 받지 못한 주자는 다음 구간에 다시 줄을 서지 않는다. 한 구간에서 사용하지 않은 종이컵은 버리지 않고 다음 구간으로 넘긴다. 물은 항상 충분하므로 물의 양은 고려하지 않는다. 사용한 종이컵은 급수대로 돌아오지 않으며, 기록에 적힌 새 종이컵 외에 재고가 늘어나는 일도 없다. 모든 구간에서 종이컵을 추가하는 일이 주자들에게 물을 나누어 주는 일보다 먼저 일어난다. 예를 들어 어떤 구간 직전에 종이컵이 2개 남아 있고 새 종이컵이 1개 도착한 뒤 주자 5명이 오면, 주자 3명은 물을 받고 나머지 2명은 물을 받지 못한다. 이 구간이 끝났을 때 남은 종이컵은 0개다. 주자들의 도착 순서는 물을 받지 못한 사람의 수에 영향을 주지 않으므로 개인별 순서나 동점 처리는 고려하지 않는다. 각 구간의 기록이 시간순으로 주어진다. N개 구간 전체에서 물을 받지 못한 주자의 수와 마지막 구간이 끝난 직후 남아 있는 종이컵의 수를 구한다. 물을 받지 못한 주자가 한 명도 없다면 그 수는 0이며, 마지막에 남은 종이컵이 없다면 남은 수는 0이다.

입력

첫째 줄에 구간의 수 N과 처음 종이컵의 수 S가 공백으로 구분되어 주어진다.
다음 N개 줄 중 i번째 줄에 i번째 구간에서 추가되는 종이컵의 수 A_i와 도착하는 주자의 수 B_i가 공백으로 구분되어 주어진다.
모든 입력값은 정수이며, 1 ≤ N ≤ 1,000, 0 ≤ S ≤ 1,000, 0 ≤ A_i ≤ 1,000, 0 ≤ B_i ≤ 1,000이다.

출력

물을 받지 못한 주자의 총수와 마지막 구간이 끝난 직후 남은 종이컵의 수를 이 순서대로 공백으로 구분하여 한 줄에 출력한다.

4 3
2 4
0 3
5 2
1 6

4 0

3 0
0 0
2 1
0 1

0 0

1 5
0 2

0 3

출처: Devin.KR 자체 제작