Police Station

Several police stations lie on an infinitely long one-dimensional number line, all at distinct coordinates. Buy exactly capacity distinct integer coordinates, none of which coincides with a police station. The cost of each plot is its distance to the nearest police station; find the minimum total cost.

输入格式

The first line contains n and capacity, and the second line contains the n distinct integer coordinates of the police stations. This site's additional constraints: 1≤n≤100000, 1≤capacity≤50000, |station[i]|≤10^9. This site's upper bounds guarantee that the worst-case answer does not exceed 625025000, which fits the original function's int return range.

输出格式

Output the minimum total cost.

样例 1

输入：

2 4
7 8

输出：

6

样例说明

Plots can only be at integer coordinates; the two available coordinates next to each police station cost 1. The original problem's constraints are missing, so this site explicitly adds upper bounds on the number of stations, the coordinates, and capacity; with capacity≤50000, even if there is only one police station, the total cost of buying the nearest capacity non-station coordinates is at most 625025000.