Convicts in jail P81991


Statement
 

pdf   zip

thehtml

There are n jails beside a straight road. You know the position (in km) of each jail. Please choose the jails where to confine m dangerous convicts in order to maximize the minimum distance between two convicts.

For instance, consider five jails at positions 1, 10, 23, 42 and 50, and three convicts. Here, the optimum solution is to use the first, third and fifth jail, with a minimum distance of 22.

Input

Input consists of several cases, each with m and n, followed by the positions of the n jails. Assume 2 ≤ mn ≤ 104, and that the n positions are different and between 0 and 109.

Output

For every case, print the largest possible distance between the two nearest convicts.

Public test cases
  • Input

    3 5  1 10 23 42 50
    2 2  1000000000 0
    4 6  4 0 2 5 3 1
    3 6  4 0 2 5 3 1
    2 6  4 0 2 5 3 1
    

    Output

    22
    1000000000
    1
    2
    5
    
  • Information
    Author
    Javier Nistal
    Language
    English
    Official solutions
    C++
    User solutions
    C++