오리와 박수치는 춘배
면접 대비시간 제한1초메모리 제한1024 MB
서로 다른 오름차순 꽥꽥 시각과 K가 주어질 때, 각 X_i마다 [X_i, X_i+K] 안에 박수가 있도록 하는 최소 박수 횟수를 구한다.
문제
춘배는 오리를 보러 왔다. 오리는 춘배가 있는 동안 총 번 "꽥꽥" 소리를 낸다. 오리의 소리를 듣고 감동받은 춘배는 오리에게 박수를 쳐준다.
오리가 초에 "꽥꽥" 소리를 낸다면 소리를 들은 춘배는 오리에게 초 이상 초 이하에 한 번 이상 박수를 쳐야한다.
만약 오리가 소리를 낸 초부터 초 사이에 한 번도 박수를 쳐주지 않는다면 실망한 오리는 집으로 가버린다. 예를 들어 라면 초, 초, 초 중 최소 한번은 박수를 쳐야 한다.

<박수를 치는 춘배의 모습>
오리가 집으로 가지 않도록 춘배가 박수를 쳐줄 때 박수를 최소 몇 번 쳐야 하는지 구해보자.
입력
첫째 줄에 오리가 "꽥꽥" 소리를 내는 횟수 와 정수 가 공백으로 구분되어 주어진다. ,
둘째 줄에 오리가 "꽥꽥" 소리를 내는 시각 이 공백으로 구분되어 주어진다. 는 서로 다르며 오름차순으로 주어진다.
출력
오리가 집으로 가지 않도록 춘배가 박수를 쳐줄 때 박수를 최소 몇 번 쳐야 하는지 출력한다.