Задачи
Города-побратимы High
Города-побратимы High
На координатной прямой расположены \textbf{N} городов. Было решено выбрать \textbf{K} различных пар этих городов и назвать города каждой пары городами-побратимами по отношению друг к другу. При этом, получается, что у каждого города может быть не более одного города-побратима. Требуется определить какое может быть максимальное и минимальное суммарное расстояние между городами-побратимами.
\textbf{Ограничения}
\textbf{N}, \textbf{K} -- целые числа. \textbf{1} ≤ \textbf{N} ≤ \textbf{100000}, \textbf{0} ≤ \textbf{K} ≤ \textbf{N/2}. Координаты городов не превышают \textbf{10^9} по абсолютной величине.
\InputFile
В первой строке содержатся числа \textbf{N} и \textbf{K}. Во второй -- \textbf{N} чисел, определяющих координаты городов.
\OutputFile
В единственной строке нужно вывести два числа -- максимальное и минимальное суммарное расстояние, которое может получиться между городами-побратимами в \textbf{K} парах.
Входные данные #1
5 2 0 3 4 7 9
Выходные данные #1
13 3