AT_abc414_d [ABC414D] Transmission Mission

There are $ N $ houses numbered from $ 1 $ to $ N $ on a number line. House $ i $ is located at coordinate $ X_i $ . Multiple houses may be located at the same coordinate. You place $ M $ base stations at arbitrary real coordinates on the number line. Then, you set a non-negative integer **signal strength** for each base station. When the signal strength of a base station is set to $ x $ , The signal from that base station reaches a house if and only if the distance between the base station and the house is at most $ \displaystyle\frac{x}{2} $ . Particularly, when $ x=0 $ , the signal reaches only houses located at the same coordinate as the base station. Find the minimum possible sum of signal strengths when the positions and signal strengths of the base stations are set such that at least one base station's signal reaches every house. It can be proved that the answer is an integer for any input satisfying the constraints.

The input is given from Standard Input in the following format: > $ N $ $ M $ $ X_1 $ $ \dots $ $ X_N $

Output the answer as an integer in one line.

### Sample Explanation 1 By placing three base stations as follows, signals reach all houses. - Place a base station with signal strength $ 5 $ at coordinate $ 7.5 $ . This base station reaches houses $ 1,2,5 $ . - Place a base station with signal strength $ 1 $ at coordinate $ 14.5 $ . This base station reaches houses $ 3,6,7 $ . - Place a base station with signal strength $ 0 $ at coordinate $ 20 $ . This base station reaches house $ 4 $ . The sum of signal strengths in this case is $ 6 $ . It is impossible to satisfy the condition with an arrangement where the sum of signal strengths is smaller than $ 6 $ , so output $ 6 $ . ### Constraints - $ 1 \leq M \leq N \leq 5 \times 10^5 $ - $ 1 \leq X_i \leq 10^{12} $ ( $ 1 \leq i \leq N $ ) - All input values are integers.