Disastrous Downtime – Kattis, Kattis (original) (raw)

Hide

Claus Rebler, cc-by-sa

You’re investigating what happened when one of your computer systems recently broke down. So far you’ve concluded that the system was overloaded; it looks like it couldn’t handle the hailstorm of incoming requests. Since the incident, you have had ample opportunity to add more servers to your system, which would make it capable of handling more concurrent requests. However, you’ve simply been too lazy to do it—until now. Indeed, you shall add all the necessary servers very soon!

To predict future requests to your system, you’ve reached out to the customers of your service, asking them for details on how they will use it in the near future. The response has been pretty impressive; your customers have sent you a list of the exact timestamp of every request they will ever make!

You have produced a list of all the nnn upcoming requests specified in milliseconds. Whenever a request comes in, it will immediately be sent to one of your servers. A request will take exactly$1000$ milliseconds to process, and it must be processed right away.

Each server can work on at most kkk requests simultaneously. Given this limitation, can you calculate the minimum number of servers needed to prevent another system breakdown?

Input

The first line contains two integers 1lenle1000001 \le n \le 100\ 0001lenle100000 and$1 \le k \le 100\ 000$, the number of upcoming requests and the maximum number of requests per second that each server can handle.

Then follow nnn lines with one integer 0letile1000000 \le t_ i \le 100\ 0000letile100000 each, specifying that the iiith request will happen tit_ iti milliseconds from the exact moment you notified your customers. The timestamps are sorted in chronological order. It is possible that several requests come in at the same time.

Output

Output a single integer on a single line: the minimum number of servers required to process all the incoming requests, without another system breakdown.

Please log in to submit a solution to this problem

Log in

You haven't made any submissions on this problem yet.