Migrated from Lutece 2863 玩偶展示

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Kanade 现在负责把一些玩偶排列在展架上。共有 $n$ 个玩偶，但是 Kanade 只能选择其中 $k$ 个放上去。展架可以看做一个数轴，每个玩偶有一个固定的位置摆放，第 $i$ 个玩偶放在位置 $x_i$ 处。Kanade 需要使得选择的这 $k$ 个玩偶之间两两距离之和最大（注意，选择的玩偶可以放在相同的位置）。

Kanade 想知道这个最大距离和是多少。

Input

第一行两个整数 $n,k\ (2\le k\le n\le 10^5)$，分别表示玩偶个数和需要选择的玩偶数。

第二行 $n$ 个整数，第 $i$ 个表示第 $i$ 个玩偶所需放置的坐标 $x_i\ (|x_i|\le 10^5)$。

Output

一行一个整数，表示选出的玩偶之间两两距离和的最大值。

Samples

5 3
5 2 3 1 5

8

Resources

The 19th UESTC Programming Contest Preliminary