보충 수조의 넘친 물

문제

한 수족관은 전시 수조에 공급할 물을 작은 보충 수조에 모아 둔다. 보충 수조에 담을 수 있는 물의 최대량은 C리터이며, 작업을 시작할 때에는 W리터가 들어 있다. 담당자는 N차례에 걸쳐 물을 보충하고 사용한다. 각 차례에는 넣을 물의 양과 꺼내려고 하는 물의 양이 정해져 있다. 한 차례의 작업은 반드시 물을 넣는 단계부터 시작한다. 보충 수조에 A리터를 한꺼번에 넣었을 때 물의 양이 C리터를 초과하면, 초과한 물은 모두 배수구로 흘러 나간다. 이때 보충 수조에는 정확히 C리터만 남는다. 넣은 뒤의 물의 양이 C리터 이하라면 배수구로 흘러 나가는 물은 없다. 배수구로 나간 물은 다시 회수하지 않는다. 물을 넣고 넘친 물을 처리한 다음에는 보충 수조에서 B리터를 꺼내 전시 수조에 공급하려고 한다. 남아 있는 물이 B리터 이상이면 정확히 B리터를 꺼낸다. 남아 있는 물이 B리터보다 적다면 남은 물을 전부 꺼내며, 보충 수조는 빈 상태가 된다. 부족한 양을 다른 곳에서 채우거나 다음 차례에 추가로 꺼내지는 않는다. 이 두 단계를 마치고 남은 물은 다음 차례로 그대로 이어진다. 작업 사이에 증발하거나 새는 물은 없으며, 물의 양은 항상 정수 리터 단위다. 전시 수조로 꺼낸 물은 배수구로 흘러 나간 물에 포함하지 않는다. 마지막 작업이 끝난 뒤 보충 수조에 남아 있는 물 역시 넘친 물에 포함하지 않는다. N차례의 작업 중 배수구로 흘러 나간 물의 총량을 구한다. 한 번도 넘치지 않았다면 총량은 0리터다.

입력

첫째 줄에 정수 N, C, W가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000, 0 ≤ W ≤ C다.
다음 N개의 줄에 각 차례의 정수 A와 B가 작업 순서대로 주어진다. 0 ≤ A, B ≤ 1,000이다.

출력

모든 작업에서 배수구로 흘러 나간 물의 총량을 리터 단위의 정수 하나로 출력한다. 넘친 물이 없다면 0을 출력한다.

3 10 6
7 4
3 12
15 2

8

2 5 0
3 5
5 5

0

2 4 4
4 0
4 4

8

출처: Devin.KR 자체 제작