시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB4771319928.947%

문제

‘최종병기 활’ 이라는 영화를 보던 지훈이는 깊은 감명을 받아 직접 활을 만들어 보기로 한다. 

활의 구조는 나무부분인 활대와 고무줄부분인 활줄로 나뉘는데, 나무로 되어있는 활대부분에 활줄을 걸어 활을 만든다. 

지훈이의 아버지는 목수이시기 때문에, 활대는 아버지에게 부탁하면 원하는 길이와 모양으로 만들어 주신다. 따라서 지훈이는 활줄을 만들기위해 고무줄을 사러 문구점에 찾아갔다.

문구점에서 고리모양의 고무줄을 사왔는데, 이 고무줄은 N 길이의 둘레를 가진다. 

그리고 고무줄에 M개의 위치에 홈이 파여 있는데, 이 고무줄은 너무 튼튼해서 홈이 파인 곳만 절단할 수 있다. 고무줄에서 홈이 파인 위치 X는 시계 12시방향을 기준으로 0부터 시작해서 시계방향으로 1씩 증가한다. 따라서 홈이 파인 위치 X는 0부터 N-1 까지의 정수로 표현된다.

아래의 [그림2]은 N = 20, M = 3, X = {2,4,6} 일 때 고무줄의 그림이다.

또한 최고의 활을 만들기위해서는 K겹의 고무줄이 필요하다. 따라서 주어진 고무줄을 적당히 절단하여 K개의 직선고무줄을 얻어낼 것이다. K겹의 직선고무줄을 겹쳐 활대에 걸게 되는데, 이때 K개의 직선고무줄 중 가장 작은 고무줄의 길이에 의해 활의 길이가 결정된다. 즉, 절단한 고무줄 중 가장 작은 고무줄의 길이가 활의 길이가 된다.

지훈이가 만들 수있는 가장 긴 활의 길이는?

입력

입력의 첫째 줄에 고무줄의 둘레 N(1 ≤ N ≤ 100000 인 정수)과 절단이 가능한 홈의 개수 M(1 ≤ M ≤ min(N,1000) 인 정수) 그리고 최고의 활을 만들때 필요한 고무줄겹의 수 K(1 ≤ K ≤ M 인 정수)가 주어진다.

이후 두 번째 줄부터 M+1번째 줄까지 고무줄에서 절단이 가능한 홈의 위치 X(0 ≤ X ≤ N-1 인 정수)가 주어진다. 주어지는 홈의 위치는 각각 유일하며 오름차순으로 주어진다.

출력

만들 수 있는 가장 긴 활의 길이를 출력하시오. 만약 활을 만들 수 없다면 -1을 출력하시오

예제 입력 1

20 3 3
2
4
6

예제 출력 1

2

예제 입력 2

20 3 1
2
4
6

예제 출력 2

20