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