문제
매년 꿀꿀이들을 위한 돌다리 건너기 축제가 열린다. 이 축제는 개울 왼쪽을 출발점으로 하여 거리 L 만큼 떨어진 개울 오른쪽 도착점으로 돌다리를 이용하여 건너가는 것이다. 출발점으로부터 도착지점까지 돌다리는 일직선 형태로 놓여 있으며 돌다리의 위치 Di는 출발점으로부터의 거리로 표시된다.
경기는 각 꿀꿀이들이 출발점에서 시작하여 도착점까지 놓여있는 돌다리를 순서대로 밟으며 가는 것이다. 물론 겁이 많거나 민첩하지 못한 꿀꿀이들은 결승점까지 가지 못하고 개울에 빠지게 된다. 작년에는 *두현꿀꿀이, *동균꿀꿀이, *승유꿀꿀이 등이 빠졌다. 물론 본인들은 날이 너무 더워 일부러 개울에 들어갔다고 한다.^^
우리의 대왕 꿀꿀이 상민이는 이 게임의 창시자로 매년 이 경기를 지켜본다. 하지만 시간이 갈수록 축제에 참여한 꿀꿀이들이 다닥다닥 붙어있는 짧은 거리에서조차도 뒤뚱거리는 모습을 보고 무언가 조치를 취해야 하겠다고 생각했다. 그래서 상민이는 꿀꿀이 위원회를 소집하여 축제에 참여한 꿀꿀이가 점프해야하는 최단거리를 늘리기 위해 돌다리 M 개를 없애기로 하였다.
상민이는 돌다리를 제거하기 전에 최단거리를 얼마나 증가시킬 수 있는지 알고 싶다. 적절한 M개의 돌다리를 없앤 뒤에 꿀꿀이가 점프해야 하는 최단거리의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫 행에 출발점과 도착점의 거리 L, 돌다리의 개수 N, 없애기로 한 돌다리의 개수 M이 공백으로 구분하여 주어진다.
( 1 ≤ L ≤1,000,000,000) ( 0 ≤ M ≤ N ≤ 50,000)
두 번째 행에서부터 N행에 걸쳐 출발점으로부터의 거리 Di가 행으로 구분되어 주어진다.( 1 ≤ Di < L)
입력되는 모든 수는 정수이다.
출력
M개의 돌다리를 없앤 뒤 축제에 참여한 꿀꿀이가 점프할 수 있는 최단거리의 최댓값을 구하여 하나의 정수로 출력하시오.
예제1
입력
2552
2
14
11
21
17
출력
4
출처
USACO 2006 December Silver