영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
In a school, there are N students who need to eat lunch in the school cafeteria every day. Just before the cafeteria opens, all the students line up outside. There are K queue spots in total, numbered from 0 to K-1. At most one person can stand at each queue spot. Some queue spots must be empty due to fire safety regulations. Specifically, there are M intervals of queue spots that must be empty – the interval l_i, r_i indicates that no one is allowed to stand on any of the spots l_i, l_i+1, …, r_i. It is guaranteed that no interval overlaps with any other.
The school principal has just heard about some kind of ”pandemic” and decides that it is time for drastic measures. The principal wants to introduce social distancing in the lunch line. He plans to choose an integer D, and then declare that each student must maintain at least a distance of D from the nearest other student. A student at queue spot i and a student at queue spot j have a distance |i-j|.
Help the principal find the largest D he can choose so that all students can still stand in the lunch line at the same time!
Input
The first line contains three integers N, M, and K (2 ≤ N ≤ 10^9, 0 ≤ M ≤ 10^5, and N ≤ K ≤ 10^12), the number of students, the number of forbidden intervals, and the number of queue spots.
Then follow M lines each with 2 integers, l_i, r_i (0 ≤ l_i ≤ r_i ≤ K-1), the start and end of interval number i. It is guaranteed that no pair of these intervals overlap, and that there are at least N queue spots that are not forbidden.
Output
Print an integer: the largest possible social distance.
Points
Your solution will be tested on several test case groups. To get the points for a group, it must pass all the test cases in the group.
| Group | Point value | Constraints |
|---|---|---|
| 1 | 11 | M = 0, N ≤ 10^6 |
| 2 | 10 | N · K · M ≤ 10^6 |
| 3 | 15 | N, M ≤ 1000, N ≤ K ≤ 2000 |
| 4 | 19 | N · M ≤ 10^7 |
| 5 | 21 | N ≤ 10^6 |
| 6 | 24 | No additional constraints. |
예제
예제 1
3 2 10 3 5 7 8
3
예제 2
4 4 30 0 8 20 24 27 29 9 9
4
예제 3
9 0 99999999999
12499999999