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