As is well known, the Jinmai Garden dumpling restaurant is known as the "Second Canteen of Beibei," carrying a special sentiment for food among Beibei students.

Jinmai Garden has $n$ types of dumplings, where the deliciousness of the $i$-th type is $a_i$.

Liangsheng and Liangcha, like NPCs, refresh their orders at the Jinmai Garden dumpling restaurant every week. Since their tastes differ, they will always choose two different types of dumplings $i$ and $j$ ($i \neq j$).

Define the "non-uniformity" of a meal choice as $S_{i,j} = |a_i - a_j|$. Now, Liangsheng asks you to choose $k$ distinct meal choices such that the sum of the "non-uniformity" of these $k$ meal choices is minimized.

Note: Two meal choices $(i_1, j_1)$ and $(i_2, j_2)$ are considered the same if and only if the sets $\{i_1, j_1\}$ and $\{i_2, j_2\}$ are the same, i.e., $(i, j)$ is an unordered pair.

Input

The first line contains two positive integers $n, k$ ($2 \le n \le 10^6, 1 \le k \le \min\{\frac{n(n-1)}{2}, 10^{11}\}$), representing the number of dumpling types and the number of meal choices, respectively.

The second line contains $n$ positive integers $a_i$ ($1 \le a_i \le 10^8$), representing the deliciousness of the $i$-th type of dumpling.

Output

Output a single integer representing the minimum sum of "non-uniformity."

Examples

Input 1

5 4
1 4 3 2 5

Output 1

4

Note

Choosing the 4 pairs $(1, 4), (2, 3), (3, 4), (2, 5)$ results in a sum of "non-uniformity" of 4.