Covering with intervals P76554


Statement
 

pdf   zip

html

Given a natural k and several numbers x1, …, xn, we want to find the smallest possible set of closed intervals of length k that cover those numbers. In other words, we must find a set of intervals {[y1, y1 + k], …, [ym, ym + k]} such that

  • for every xi, there exists some j such that xi ∈ [yj, yj + k];
  • m is minimum.

For instance, if k=10 and the xi’s are 14, 19, 23 and 27, a possible solution is {[12, 22], [1.8, 2.8]}, since every xi belongs to (at least) one of the two intervals, and it is not possible to cover the four numbers with a single interval.

Input

Input consists of several cases, each of which starts with k, followed by n, followed by n different numbers. All numbers in the input are integers. Assume 1 ≤ k, n ≤ 105.

Output

For every case, print the minimum number of closed intervals of length k that cover the given numbers.

Public test cases

  • Input

    10  4  14 19 23 27
100 6  175 350 50 300 150 20
10  2  -25 -35

    Output

    2
3
1
    • Information
    Author
    Enric Rodriguez
    Language
    English
    Translator
    Enric Rodriguez
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++