## Computer Science

View as PDF

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 512M
Author:

Problem type

##### 2017 Fall Waterloo Local ACM Contest, Problem C

Vera has integers . A margin is a non-negative integer such that it is possible to choose integers such that for all , , the interval contains at least of Vera's integers and also contains .

Compute the minimum possible margin.

#### Input

Line contains integers and .

Line contains integers, .

#### Output

Print one line with one integer, the minimum possible margin.

#### Sample Input

5 3
1 -2 10 5 4

#### Sample Output

6

#### Note

For the first example, one possible solution is to choose , which is illustrated below.