Data Reorganization

Given an array data of n positive integers. In each operation, choose two different indices i<j of the current array and append |data[i]-data[j]| to the end. The original elements are kept; later operations may choose new elements and may also reuse index pairs chosen before. Perform exactly k operations and find the smallest value that the minimum element of the final array can reach. Appended values may be 0. This site's standard input/output is compiled from the complete fixed original source, without narrowing the original ranges.

输入格式

The first line contains n and k, and the second line contains n integers data[i]. 2≤n≤2000, 1≤data[i]≤10^9, 1≤k≤10^9. The initial array may contain duplicate values.

输出格式

Output one integer: the smallest possible value of the array's minimum element after exactly k operations.

样例 1

输入：

6 2
42 47 50 54 62 79

输出：

3

样例 2

输入：

5 1
4 2 5 9 3

输出：

1

样例 3

输入：

5 2
5 18 3 12 11

输出：

1

样例说明

In example 1, you can pick 47 and 50 twice and append two 3s, so the minimum after two steps is 3; there is no third step to produce 0. In example 2, pick 4 and 5 to append 1. In example 3, pick 12 and 11 to append 1 and then perform any valid operation; the minimum is still 1. All three examples come from the original statement; the explanations of the operations were completed by this site.