gshscs

시간 제한 2초

메모리 제한 65536KB

문제 설명

 매년 소를 위한 특이한 형태의 징검다리 건너기 축제가 열리는데, 이것은 강에서 한 바위에서 다른 바위 위로 조심스럽게 뛰어다니는 것이다. 길고 직선인 강에서 출발점의 바위에서부터 L 유닛의 거리를 지나 결승점의 바위로 가는 것이다. 출발점의 바위에서부터 Di의 거리만큼 동일하게 간격을 두고 있다.

 경기는 각 소들이 차례로 출발점에서 시작하여 결승점까지 도달하는 것인데 바위에서 바위로 점프해야만 한다. 물론 민첩하지 못한 소들은 결승점까지 갈 수 없을 것이며 대신 강 속에 빠지고 말 것이다.

 FJ는 자신의 소를 매우 자랑스럽게 여기기 때문에 매년 이 경기를 지켜본다. 하지만 시간이 갈수록 다른 농부들의 소심한 소들이 다닥다닥 붙어있는 짧은 거리에서조차도 뒤뚱거리는 경기를 관람하는 것이 지겨워졌다. 그래서 그는 소가 점프해야하는 최단거리를 늘리기 위해 몇 개의 바위를 없애기로 결심했다. 물론 출발점과 결승점의 바위는 없애면 안된다. 하지만 그는 M개의 바위를 제거하려고 계산하고 있다.

 FJ는 바위를 제거하기 "전에" 최단거리를 얼마나 증가시킬 수 있는지 알고 싶어한다. 적절한 M개의 바위를 없앤 뒤에 소가 점프해야 하는 최단거리의 최대값을 구할 수 있도록 FJ를 도와라.

입력

Line 1:공백으로 구분된 정수 L,N,M이 온다.(1<=L<=1,000,000,000, 0<=M<=N<=50,000)

Line 2~Line N+1:각 줄에 출발점으로부터 바위들이 얼마나 멀리 떨어져 있는지를 나타내는 하나의 정수가 온다. 두 바위는 같은 위치에 있을 수 없다.

출력

M개의 바위를 치운 뒤 소가 점프할 수 있는 최단거리의 최대값을 나타내는 하나의 정수가 온다.

입력 예제

25 5 2

2

14

11

21

17

출력 예제

4

http://poj.org/problem?id=3258