제자리멀리뛰기 timer 1s memory 256MB

KOI고등학교에서는 체력 측정에서 제자리멀리뛰기가 가장 중요하다. KOI의 체육선생님께서는 학생들의 제자리멀리뛰기 실력을 키우기 위해 특수 훈련을 준비 중이다.

특수 훈련 장소는 KOI고등학교 특수 트레이닝 센터로 이 곳은 끓는 용암으로 가득 차 있다. 체육 선생님께서는 이 용암으로 가득찬 방의 가운데 있는 돌섬에 학생들을 가두고 학생들이 탈출해 나오기를 기대하고 있다.

탈출할 수 있는 방법은 단 한 가지뿐이다. 돌섬에서 탈출구까지 띄엄띄엄 존재하는 작은 돌섬들로 점프하여 탈출구까지 가는 것이다.

돌섬에서 탈출구 사이에는 총 n개의 작은 돌섬이 있다. 선생님은 이 n개의 작은 돌섬들 중 m개를 제거하여 학생들이 최대한 멀리뛰기 연습의 효율을 높이고, 학생들이 각 돌섬을 점프한 거리의 최솟값을 최대한 크게 하려고 한다.  물론 학생들은 체력이 좋기 때문에 두 돌섬이 아무리 멀더라도 점프할 수 있다. 즉, 빠지는 일은 없다. 그리고 학생들은 탈출 시 n-m개의 모든 돌섬을 밟으면서 탈출해야 한다.

학생들이 갇힌 돌섬으로부터 탈출구까지의 거리 d가 주어지고, 각 n개의 작은 돌섬의 위치(갇힌 돌섬으로 부터의 거리)가 주어지며, 제거할 수 있는 작은 돌섬의 수 m이 주어질 때, m개를 제거한 후 학생들이 점프하는 최소거리의 최댓값을 구하는 프로그램을 작성하시오.​