서버 증설 계획

얼마 전 시스템이 멈춘 원인을 조사한 결과, 밀려드는 요청을 감당하지 못하고 과부하가 걸린 것으로 드러났다. 서버를 더 붙이면 동시에 처리하는 요청 수가 늘어나지만, 여태 미루기만 했다. 이제는 정말 필요한 만큼 서버를 늘리려고 한다.

앞으로 들어올 요청을 예측하려고 고객들에게 사용 계획을 물었더니, 앞으로 보낼 모든 요청의 정확한 시각을 그대로 알려 주었다. 그래서 다가올 요청 $n$개의 시각을 밀리초 단위로 정리했다.

요청이 들어오면 곧바로 서버 하나로 보내지고, 처리를 미룰 수 없다. 처리에는 정확히 1000밀리초가 걸린다. 즉 시각 $t$에 도착한 요청은 $t$부터 $t + 1000$ 직전까지 서버를 붙잡고 있고, 시각 $t + 1000$에는 이미 손을 뗀 상태다.

서버 한 대는 동시에 최대 $k$개의 요청을 처리한다. 이 조건에서 시스템이 다시 멈추지 않게 하려면 서버가 최소 몇 대 필요한지 구하라.

첫째 줄에 다가올 요청의 수 $n$과 서버 한 대가 동시에 처리하는 요청 수 $k$가 주어진다. ($1 \le n \le 100000$, $1 \le k \le 100000$)

다음 $n$개 줄에 각 요청의 시각 $t_i$가 한 줄에 하나씩 주어진다. ($0 \le t_i \le 100000$) 시각은 고객에게 연락한 순간을 기준으로 한 밀리초 단위이며, 시간 순으로 정렬되어 있다. 같은 시각에 여러 요청이 들어오기도 한다.

모든 요청을 처리해 시스템이 다시 멈추지 않게 하는 데 필요한 서버의 최소 개수를 한 줄에 출력한다.