징검다리 - 구름LEVEL
징검다리
Quiz Info
Quiz Info
징검다리
100points
Participant
7
Solved Rate
57.1%
0
2

구름이는 여행을 하던 중에 징검다리를 마주하게 되었습니다. 이 징검다리를 건너지 않으면 구름이는 여행 일정에 차질이 생기게 됩니다.

출발점에서 도착점까지 띄엄띄엄 놓아진 징검돌을 점프하여 도착점까지 가야 한다고 합니다. 출발점에서 도착점 사이에는 총 n개의 작은 징검돌이 있습니다. 그러나 장마철에 비가 많이와서 징검돌들 중 m개가 물에 잠긴 상황입니다.

구름이는 징검돌 사이가 아무리 멀더라도 점프할 수 있습니다. 즉, 징검돌을 건너다 물에 빠지는 일은 없습니다. 그리고 구름이는 (n - m)개의 모든 징검돌을 밟으면서 징검다리를 건너야 합니다.

출발점부터 도착점까지의 거리 d가 주어지고 각 n개의 징검돌의 위치(출발점 0으로부터의 거리)가 주어지며 물에 잠긴 징검돌의 수 m이 주어질 때, 징검돌 n개 중 m개를 제거한 후 구름이가 점프하는 최소거리의 최댓값을 구하는 프로그램을 작성하십시오.

* 힌트 : 거리 d 미만으로는 점프하지 않도록 m개의 돌을 제거할 수 있는가 ?


입력

첫 번째 줄에는 출발점으로부터 도착점까지의 거리 d(1 ≤ d ≤ 1,000,000,000), 징검돌의 수 n(0 ≤ n ≤ 50,000), 장마로 물에 잠긴 징검돌의 수 m(0 ≤ m ≤ n)

두 번째 줄부터 n줄에 걸쳐서 출발점으로부터 각 징검돌이 얼마나 떨어져 있는지를 나타내는 하나의 정수가 한줄에 하나씩 주어집니다.

*두 징검돌은 같은 위치에 있을 수 없으며, 장마로 물에 잠긴 징검돌은 어떤 징검돌이든 될 수 있습니다.

출력

구름이가 점프할 수 있는 최소거리의 최댓값




Input/Output Example
:
Blank
:
Line Break
:
Tab
Example 1
Input
2552
2
14
11
21
17
Output
4
Example 2
Input
2041
2
14
11
17
Output
3
⋇ Please keep the input and output formats carefully
Quiz Info
Q & A
Q&A forum that anyone can ask and answer.
Share your questions and answers with other students and grow together!

Registered Questions(0)