27977번 - 킥보드로 등교하기

건덕이는 이번 학기 수강신청을 실패해 1교시 수업을 잔뜩 듣게 되었다! 건덕이의 등교 시간은 직장인의 출근 시간과 겹치는 시간대였기 때문에, 지하철을 타지 않고 킥보드를 구매해서 등교하기로 한다.

킥보드는 배터리 $1$을 소모해 거리 $1$만큼 이동할 수 있으며, 배터리를 모두 사용하면 킥보드가 멈추기 때문에 소진되기 전에 충전소에서 충전을 해야 한다.

건덕이의 집과 학교는 각각 $0$, $L$ 위치에 자리 잡고 있으며, 등굣길에는 총 $N$개의 킥보드 충전소가 순서대로 자리 잡고 있다. 충전하느라 시간을 낭비한다면 지각할 게 뻔하기 때문에, 건덕이는 등교 중에 최대 $K$번 충전소에 방문하기로 했다. 충전소에 방문하면 킥보드의 배터리가 가득 찬다.

킥보드의 가격과 배터리 용량은 비례하며, 건덕이는 집에서 킥보드를 가득 충전한 상태로 집을 나선다.

건덕이는 조건을 만족하는 킥보드 중에서도 가장 싼 킥보드를 구매하고자 한다. 건덕이가 구매할 킥보드의 배터리 용량을 구해보자.

첫 번째 줄에 학교까지의 거리, 킥보드 충전소의 개수, 최대 충전소 방문 횟수를 나타내는 세 정수 $L, N, K$가 공백으로 구분되어 주어진다.

두 번째 줄에 $i$번째 충전소의 위치를 나타내는 $N$개의 정수 $A_i$가 공백으로 구분되어 주어진다.

건덕이가 구매해야 할 킥보드의 배터리 용량을 출력한다.

• $5 \le L \le 200\,000$
• $3 \le N \le \min(L - 1, 100\,000)$
• $0 \le K \le N$
• $1 \le A_i \lt L$
• $1 \le i \lt N$인 모든 정수 $i$에 대해서 $A_i \lt A_{i+1}$

첫 번째 예제 입력에서 충전을 위해 방문하는 충전소는 $A_i = 3$ 지점의 충전소와 $A_i = 6$ 지점의 충전소이다.