## Problem D. Hall of water life ≡

 Author: A. Klenin Time limit: 3 sec Input file: input.txt Memory limit: 256 Mb Output file: output.txt

### Statement

The main hall of the Nearsea Institute of Unspecified Underwater Studies has a shape of a long corridor. Along the corridor, there are N aquariums exhibiting various sea creatures. Aquariums are located at distances x1, …, xN from the hall entrance (xi < xi + 1).

The institute has recently got a new director, who decided that the aquarium maintenance is too costly, and issued an order to remove M (0 ≤ M ≤ N − 2) aquariums.

To minimize the disruption to the looks of the hall, it was decided that:

1. the first and the last aquariums should be left in their places;
2. the maximum distance between the adjacent aquariums must be as small as possible.

Your program must select aquariums for removal in such a way that the above conditions are satisfied.

### Input file format

Input file contains integers N M followed by N integers xi.

### Output file format

Output file should contain a single integer — the smallest possible maximum distance.

### Constraints

2 ≤ N ≤ 400, 1 ≤ xi ≤ 109,

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
5 2
1 2 3 4 5

2
2
4 1
10 21 30 40

19


0.037s 0.008s 15