题目描述

Mirko's newest math homework assignment is a very difficult one! Given a sequence, $V$, of $N$ integers, remove exactly $K$ of them from the sequence. Let $M$ be the largest difference of any two remaining numbers in the sequence, and $m$ the smallest such difference. Select the $K$ integers to be removed from $V$ in such a way that the sum $M + m$ is the smallest possible. Mirko isn't very good at math, so he has asked you to help him!

输入格式

The first line of input contains two positive integers, $N$ ($3 \leq N \leq 1\,000\,000$) and $K$ ($1 \leq K \leq N - 2$).

The second line of input contains $N$ space-separated positive integers – the sequence $V$ ($-5\,000\,000 \leq V_i \leq 5\,000\,000$).

输出格式

The first and only line of output must contain the smallest possible sum $M + m$.

5 2
-3 -2 3 8 6

7

6 2
-5 8 10 1 13 -1

13

6 3
10 2 8 17 2 17

6