휴게소 세우기

다솜이는 길이가 L인 유료 고속도로를 운영한다. 현재 고속도로에는 N개의 휴게소가 있으며, 각 휴게소의 위치는 고속도로 시작점에서 떨어진 거리로 주어진다. 다솜이는 휴게소를 M개 더 세우려고 한다.

새 휴게소는 이미 휴게소가 있는 위치, 고속도로의 시작점, 고속도로의 끝점에는 세울 수 없다. 휴게소는 정수 위치에만 세울 수 있다.

고속도로의 시작점과 끝점도 휴게소가 없는 구간의 경계로 본다. 다솜이는 휴게소를 반드시 M개 모두 추가한 뒤, 휴게소가 없는 연속 구간의 길이 중 최댓값을 가능한 작게 만들고 싶다. 그 최솟값을 구하라.

고속도로의 길이가 1000이고 현재 휴게소가 {200, 701, 800}에 있으며 휴게소를 1개 더 세운다고 하자. 처음에는 휴게소가 없는 구간 중 200부터 701까지의 길이 501이 가장 길다. 새 휴게소를 위치 451에 세우면 가장 긴 구간의 길이가 251이 되고, 이보다 더 작게 만들 수 없다.

첫째 줄에 현재 휴게소의 개수 N, 더 지으려는 휴게소의 개수 M, 고속도로의 길이 L이 공백으로 구분되어 주어진다.

둘째 줄에는 현재 휴게소의 위치가 공백으로 구분되어 주어진다. N = 0이면 둘째 줄은 비어 있을 수 있다.

휴게소를 M개 모두 지은 뒤, 휴게소가 없는 구간 길이의 최댓값이 가질 수 있는 최솟값을 출력한다.

• 0 ≤ N ≤ 50
• 1 ≤ M ≤ 100
• 100 ≤ L ≤ 1,000
• 1 ≤ 휴게소의 위치 ≤ L - 1
• N + M < L
• 모든 휴게소의 위치는 서로 다르다.
• 입력으로 주어지는 모든 수는 정수이다.