가로등

각각 좌우로 K미터를 비추는 가로등들이 있을 때, 1번부터 N번까지 모든 미터를 밝히기 위해 추가로 필요한 가로등의 최소 개수를 구한다.

보통4그리디정렬구간구현면접 대비아직 제출이 없습니다시간 제한1초메모리 제한64 MB

문제

대림절이 되었다. 길이가 NN미터인 거리에 가로등 MM개가 서 있다. 거리의 각 미터에는 1번부터 NN번까지 번호가 붙어 있다. 가로등은 자신이 놓인 미터와 그 좌우로 KK미터씩을 밝힌다. 즉 XX번 미터에 놓인 가로등은 XKX - K번부터 X+KX + K번까지를 모두 밝힌다. 한 미터를 여러 가로등이 함께 밝혀도 상관없다. 가로등의 위치는 모두 다르다.

지금 서 있는 가로등만으로는 거리 NN미터가 전부 밝지 않을 수 있다. 거리 전체가 밝아지도록 1번과 NN번 사이의 위치에 가로등을 더 세우려고 한다. 추가로 필요한 가로등의 최소 개수를 구하여라.

입력

첫째 줄에 NN이 주어진다. (1N10001 \le N \le 1000)

둘째 줄에 MM이 주어진다. (1MN1 \le M \le N)

셋째 줄에 KK가 주어진다. (0KN0 \le K \le N)

이어지는 MM개의 줄에 가로등의 위치가 한 줄에 하나씩 오름차순으로 주어진다. 위치는 서로 다르고 모두 1 이상 NN 이하이다.

출력

추가로 세워야 하는 가로등의 최소 개수를 출력한다.

힌트

첫 번째 예제에서는 NN미터가 이미 모두 밝으므로 가로등을 더 세우지 않아도 된다.

세 번째 예제에서는 가로등 하나를 더 세워야 한다. 예를 들어 13번 미터에 세우면 된다.