영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
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.
| Group | Points | Constraints |
|---|---|---|
| 1 | 10 | N=1 |
| 2 | 25 | N ≤ 1000 |
| 3 | 30 | T ≤ 10^6 |
| 4 | 35 | No 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