루미 알고리즘

#1582플래티넘Vasaloppet

PO 2024 결선코딩출제 Nils Gustafsson영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

Charlotte is watching Vasaloppet on TV. The broadcast starts at second 0 and ends at second T. Unfortunately, there are also N ad breaks, lasting during N non-overlapping intervals of seconds between second 0 and second T. Charlotte becomes very inspired by seeing the competitors at the starting line and wants to go skiing herself during the race. The skiing trip takes S seconds, and she must be back by second T (to see who wins).

Charlotte wants to go on her skiing trip at a time when she misses as little of Vasaloppet as possible. Your task is to calculate the minimum number of seconds of Vasaloppet that Charlotte can miss if she optimally chooses when to go on her skiing trip. Missed seconds are the seconds when Charlotte is out on her skiing trip while there is no ad break running.

(그림은 원문 저장소에서 볼 수 있습니다)

Figure 1: The picture describes the first sample case. The red rectangles are the ad breaks. If Charlotte starts her skiing trip when the first ad break starts and gets back home when the second break ends, she only misses 2 seconds of Vasaloppet.

Input

The first line of input contains three integers N, T, and S (0 ≤ N ≤ 10^5, 1 ≤ S ≤ T ≤ 10^9). N is the number of ad breaks, T is the duration of the broadcast in seconds, and S is the length of the skiing trip in seconds.

The following N lines each contain two integers l_i, r_i (0 ≤ l_i < r_i ≤ T), indicating that the i-th commercial break lasts from second l_i to second r_i. The commercial breaks are given in the order they occur, and all breaks are disjoint and sorted, which means that r_i < l_{i+1} for i < N.

Output

Print an integer, the minimum number of seconds that Charlotte can miss of Vasaloppet during her skiing trip if it is chosen optimally. Note that the skiing trip can end exactly at second T. For example, the skiing trip can cover the entire duration of Vasaloppet if S=3 and T=3.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

GroupPointsConstraints
110N=1
225N ≤ 1000
330T ≤ 10^6
435No additional constraints.

예제

예제 1

입력
2 10 5
1 2
4 6
출력
2

예제 2

입력
4 10 7
0 2
3 4
5 6
9 10
출력
3

예제 3

입력
0 1000000000 1000000000
출력
1000000000

출처 표기

출처: Programmeringsolympiaden 2024년 결선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.