루미 알고리즘

#1510플래티넘Social Distancing

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

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

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.

GroupPoint valueConstraints
111M = 0, N ≤ 10^6
210N · K · M ≤ 10^6
315N, M ≤ 1000, N ≤ K ≤ 2000
419N · M ≤ 10^7
521N ≤ 10^6
624No 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

출처 표기

출처: Programmeringsolympiaden 2021년 결선 · 원문 페이지 · 이용 조건 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). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.