Minimum Machines for Delayed Tasks Scheduling

You are given that CEOI received M tasks over N days. Each task requires 1 machine for 1 day. A machine can work on at most one task per day. When a task is submitted on day \(S\), it must be completed before day \(S+D\), i.e. it must be scheduled on some day in the interval \([S, S+D-1]\). Under these constraints, determine the minimum number of machines required to complete all tasks.

Note: You are allowed to schedule a task on any day in its allowed interval. The goal is to minimize the maximum number of tasks that need to be processed on any single day (which translates to the minimum number of machines needed).

inputFormat

The first line contains three integers \(N\), \(M\), and \(D\) where:

• \(N\) is the total number of days during which tasks are submitted.
• \(M\) is the number of tasks.
• \(D\) is the maximum number of days a task can be delayed.

The second line contains \(M\) integers \(S_1, S_2, \ldots, S_M\) where each \(S_i\) represents the day on which the \(i\)-th task was submitted. (Days are 1-indexed.)

outputFormat

Output a single integer: the minimum number of machines required so that every task can be scheduled on some day in its allowed interval.

sample

5 3 2
1 2 3

1