최종병기 활

지훈이는 활을 직접 만들어 보기로 했다. 활은 나무로 된 활대와 고무줄로 된 활줄로 이루어지고, 활대에 활줄을 걸면 완성된다. 아버지가 목수라서 활대는 원하는 길이와 모양으로 만들어 주신다. 그래서 지훈이는 활줄에 쓸 고무줄만 준비하면 된다.

문구점에서 사 온 고무줄은 둘레가 $N$인 고리 모양이다. 이 고무줄에는 홈이 $M$개 파여 있고, 고무줄이 워낙 튼튼해서 홈이 파인 자리에서만 자를 수 있다. 홈의 위치 $X$는 시계 12시 방향을 $0$으로 두고 시계 방향으로 $1$씩 커지므로, $0$ 이상 $N-1$ 이하의 정수다.

좋은 활을 만들려면 활줄이 $K$겹이어야 한다. 그래서 고리를 알맞게 잘라 직선 고무줄 $K$개를 얻는다. 이 $K$개를 겹쳐 활대에 거는데, 활의 길이는 그중 가장 짧은 고무줄의 길이로 정해진다.

지훈이가 만들 수 있는 가장 긴 활의 길이를 구하라.

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

첫째 줄에 고무줄의 둘레 $N$, 자를 수 있는 홈의 개수 $M$, 활에 필요한 고무줄 겹의 수 $K$가 주어진다. 세 값은 모두 정수이고 $1 \le N \le 100000$, $1 \le M \le \min(N, 1000)$, $1 \le K \le M$이다.

둘째 줄부터 $M$개의 줄에 홈의 위치 $X$가 한 줄에 하나씩 주어진다. $X$는 $0 \le X \le N-1$인 정수이고, 홈의 위치는 서로 다르며 오름차순으로 주어진다.

만들 수 있는 가장 긴 활의 길이를 출력한다. 활을 만들 수 없으면 -1을 출력한다.