카페의 컵 보충 기록

문제

작은 카페에서는 음료를 담을 깨끗한 컵을 준비대에 올려 두고 사용한다. 준비대에는 컵을 최대 K개까지 놓을 수 있다. 영업 기록을 읽기 시작하는 순간 준비대에는 컵이 S개 있으며, 이 컵은 모두 바로 사용할 수 있다. 카페 직원은 이어지는 N개 시점에 대해 새로 도착한 깨끗한 컵의 수와 손님이 요청한 음료의 수를 차례로 기록했다. 각 시점에는 반드시 컵 보충을 먼저 처리하고 음료 요청을 나중에 처리한다. 먼저 해당 시점에 도착한 컵 A개를 준비대에 올린다. 기존 컵과 도착한 컵을 합친 수가 K보다 크면 준비대에는 K개만 남긴다. 이때 남는 컵은 다른 공간으로 옮기며, 이후 시점에는 다시 가져오지 않는다. 도착한 컵의 수가 0인 경우에는 기존 컵의 수가 그대로 유지된다. 보충을 마친 뒤에는 해당 시점의 음료 요청 B잔을 처리한다. 음료 한 잔을 제공할 때마다 준비대의 컵을 정확히 하나 사용한다. 컵이 충분하면 요청한 음료를 모두 제공하고, 컵이 부족하면 준비대에 있는 컵의 수만큼만 제공한다. 제공하지 못한 요청은 즉시 취소되며 다음 시점으로 넘어가지 않는다. 사용한 컵도 이 기록 안에서는 다시 돌아오지 않는다. 직원은 모든 시점에서 실제로 제공한 음료의 수를 합쳐 영업 기록에 적으려고 한다. 준비대에 남은 컵의 수나 취소된 요청의 수는 출력하지 않는다. 모든 기록은 입력된 순서대로 처리하며, 나중에 도착할 컵으로 앞선 시점의 요청을 처리할 수 없다. 요청이 한 번도 없거나 어떤 음료도 제공하지 못했다면 합계는 0이다. 주어진 기록으로 실제 제공한 음료의 총수를 구한다.

입력

첫째 줄에 정수 N, K, S가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 1,000, 1 ≤ K ≤ 1,000, 0 ≤ S ≤ K이다.
다음 N개 줄의 i번째 줄에 해당 시점에 도착한 컵의 수 A_i와 요청한 음료의 수 B_i가 공백으로 구분되어 주어진다. A_i와 B_i는 정수이며 0 ≤ A_i, B_i ≤ 1,000이다. 줄의 순서가 시점의 순서이다.

출력

실제로 제공한 음료의 총수를 정수 하나로 출력한다.

3 5 2
4 3
0 4
5 2

7

2 3 0
0 2
0 0

0

2 4 4
4 0
0 6

4

출처: Devin.KR 자체 제작