정리 직후의 우편 바구니

문제

우체국의 분류대 옆에는 아직 정리하지 않은 편지를 담는 바구니가 있다. 업무를 시작할 때 바구니에는 이미 B개의 편지가 들어 있다. 직원은 이후 N차례에 걸쳐 새로 도착한 편지를 바구니에 넣고, 바구니에 있는 편지 중 일부를 정리해 다른 곳으로 옮긴다. 각 차례가 끝나면 바구니에 남은 편지의 개수를 기록한다. 한 차례의 작업은 반드시 정해진 순서대로 진행된다. 먼저 그 차례에 도착한 A개의 편지를 모두 바구니에 넣는다. 그다음 바구니에서 D개의 편지를 꺼내 정리한다. 정리한 편지는 다시 바구니에 들어오지 않는다. 각 차례의 D는 새 편지를 넣은 직후 바구니에 들어 있는 편지의 개수 이하이므로, 정리할 편지가 부족한 경우는 없다. 직원은 하루의 기록에서 두 수를 확인하려 한다. 첫 번째 수는 모든 차례가 끝난 뒤 바구니에 남은 편지의 개수다. 두 번째 수는 업무를 시작하기 직전과 각 차례의 작업이 완전히 끝난 직후에 확인한 편지 개수 중 가장 큰 값이다. 새 편지를 넣고 아직 정리하지 않은 중간 순간의 개수는 두 번째 수를 구할 때 사용하지 않는다. 업무 시작 직전의 B도 최댓값을 정하는 기록에 포함된다. 따라서 이후 모든 기록이 B보다 작아도 최댓값은 B다. 같은 최댓값이 여러 번 나타나면 그 값만 한 번 출력하며, 몇 번째 차례였는지는 구하지 않는다. 바구니가 비어 있는 기록도 올바른 기록이고 그때의 편지 개수는 0이다. 작업 도중 기록된 수를 임의로 초기화하지 않으며, 한 차례가 끝나고 남은 편지는 다음 차례까지 그대로 유지된다. 처음 편지 개수와 각 차례의 작업 내역이 주어질 때 두 수를 구하는 프로그램을 작성한다.

입력

첫째 줄에 작업 차례 수 N과 처음 편지 개수 B가 공백으로 구분되어 주어진다. N과 B는 정수이며, 1 ≤ N ≤ 1,000, 0 ≤ B ≤ 1,000이다. 다음 N개의 줄에는 작업 순서대로 두 정수 A와 D가 주어진다. 0 ≤ A ≤ 1,000, 0 ≤ D ≤ 1,000이며, D는 해당 차례에 새 편지를 넣은 직후의 편지 개수 이하임이 보장된다.

출력

모든 작업이 끝난 뒤 남은 편지 개수와, 업무 시작 직전 및 각 차례 종료 직후의 편지 개수 중 최댓값을 이 순서대로 공백으로 구분하여 출력한다.

4 5
7 3
2 8
0 3
6 1

5 9

2 8
10 10
0 8

0 8

1 0
0 0

0 0

출처: Devin.KR 자체 제작