주차장의 구간 기록

문제

한 주차장은 차량이 머문 시간을 확인하기 위해 하루의 운영 시간을 길이가 같은 여러 구간으로 나누어 기록한다. 각 구간의 길이는 정확히 1분이며, 운영하는 구간은 모두 N개다. 관리자는 각 구간이 시작될 때 들어온 차량 수와 나간 차량 수를 기록한다. 운영을 시작하기 전에는 주차장에 차량이 한 대도 없다. 각 구간의 시작에서는 먼저 나가는 차량이 모두 나간 뒤, 들어오는 차량이 모두 들어온다. 나가는 차량은 반드시 직전 구간까지 주차장에 있던 차량이다. 같은 구간이 시작될 때 새로 들어오는 차량이 곧바로 나가는 일은 없다. 출입 처리가 끝나면 다음 구간이 시작될 때까지 차량의 출입은 없으며, 그때 주차장에 남아 있는 모든 차량이 해당 구간의 1분을 머문다. 관리자는 차량별 기록 대신 전체 차량의 이용량을 구하려 한다. 한 차량이 한 구간을 머물면 이용량이 1만큼 늘어난다. 따라서 어떤 구간에 차량이 4대 남아 있다면 그 구간의 이용량은 4다. 같은 차량이 여러 구간 동안 계속 주차되어 있으면 머문 구간마다 이용량에 포함한다. 전체 이용량은 N개 구간의 이용량을 모두 더한 값이다. 마지막 구간이 끝난 뒤에도 차량이 남아 있을 수 있다. 이 차량들에 대해서도 마지막 구간까지의 이용량만 계산하며, 이후에 머무는 시간은 더하지 않는다. 운영 중 차량 수가 주차장의 수용 가능 대수를 넘는 입력은 주어지지 않는다. 모든 구간에 차량이 없다면 전체 이용량은 0이다. 주어진 출입 기록을 순서대로 반영하여 전체 이용량을 구하는 프로그램을 작성한다.

입력

첫째 줄에 구간 수 N과 주차장의 수용 가능 대수 C가 공백으로 구분되어 주어진다. N과 C는 정수이며 1≤N≤1,000, 1≤C≤1,000이다.
다음 N개 줄의 i번째 줄에 i번째 구간이 시작될 때 들어오는 차량 수 A_i와 나가는 차량 수 D_i가 주어진다. 두 수는 정수이며 0≤A_i,D_i≤C다. 직전 구간의 차량 수를 P라고 할 때 0≤D_i≤P이고 0≤P-D_i+A_i≤C임이 보장된다. 첫 구간 직전의 P는 0이다.

출력

전체 이용량을 정수 하나로 출력한다. 단위는 출력하지 않는다.

4 5
2 0
3 1
0 2
1 2

9

3 2
0 0
0 0
0 0

0

1 7
7 0

7

출처: Devin.KR 자체 제작