배식대의 다음 모둠

문제

학교 급식실에서는 학생들이 모둠별로 배식대에 도착한다. 배식대 담당자는 모둠이 도착할 때마다 준비된 식판의 수를 확인하고, 정해진 규칙에 따라 그 모둠을 안내한다. 모든 학생은 식판을 정확히 하나씩 사용하며, 한 번 학생에게 건넨 식판은 이번 배식이 끝날 때까지 돌아오지 않는다. 처음 배식대에 놓인 식판은 S개다. 이후 N개의 모둠이 번호 순서대로 도착한다. i번 모둠이 도착하기 직전에는 세척실에서 식판 A_i개를 가져와 배식대에 더한다. 식판을 가져오는 일은 그 모둠의 인원수와 관계없이 항상 먼저 진행한다. 배식대에 놓을 수 있는 식판 수에는 별도의 제한이 없으며, 가져온 식판은 모두 사용할 수 있다. i번 모둠의 학생 수는 B_i명이다. 식판을 더한 뒤 배식대에 남아 있는 식판이 B_i개 이상이면 그 모둠의 모든 학생에게 식판을 하나씩 건넨다. 이때 배식한 학생 수는 B_i명 늘어나고, 남은 식판 수는 B_i개 줄어든다. 식판이 정확히 B_i개 남아 있어도 정상적으로 배식한다. 반대로 식판이 B_i개보다 적으면 그 모둠은 다른 배식대로 이동한다. 이 경우 그 모둠의 일부 학생에게만 식판을 주지는 않으며, 배식대의 식판도 하나도 사용하지 않는다. 이동한 모둠은 다시 돌아오지 않는다. 따라서 앞 모둠을 보내지 못했더라도 남은 식판과 나중에 추가되는 식판으로 뒤 모둠을 배식할 수 있다. 모든 모둠을 처리한 뒤, 이 배식대에서 식판을 받은 학생의 총수와 배식대에 남은 식판 수를 구한다. 한 모둠도 배식하지 못했다면 식판을 받은 학생의 총수는 0이다. 모둠의 처리 순서를 바꾸거나 식판을 미리 빌려 쓸 수는 없다.

입력

첫째 줄에 모둠 수 N과 처음 식판 수 S가 공백으로 구분되어 주어진다. 다음 N개 줄 중 i번째 줄에 추가되는 식판 수 A_i와 모둠의 학생 수 B_i가 공백으로 구분되어 주어진다. 모든 입력은 정수이며, 1 ≤ N ≤ 1,000, 0 ≤ S ≤ 1,000, 0 ≤ A_i ≤ 1,000, 1 ≤ B_i ≤ 1,000이다.

출력

식판을 받은 학생의 총수와 모든 모둠을 처리한 뒤 남은 식판 수를 순서대로 공백 하나로 구분하여 한 줄에 출력한다.

4 3
2 4
0 3
5 2
1 5

11 0

3 0
0 2
1 3
0 2

0 1

2 2
0 2
3 3

5 0

출처: Devin.KR 자체 제작