Мішки з вівсом

Обмеження: 2 сек., 512 МіБ

У Зеника з Марічкою на фермі є \(n\) жеребців, пронумерованих від \(1\) до \(n\). Біля кожного коня стоїть свій мішок з вівсом. У мішку \(i\)-ого коня є \(a_i\) кг вівса.

За один хід можна виконати одну з двох дій:

• додати один кілограм вівса до мішка будь-якому коню,

• забрати один кілограм вівса з мішка будь-якого коня.

Зеник з Марічкою хочуть, щоб на фермі можна було знайти \(k\) жеребців, які мають однакову масу вівса у своїх мішках.

За яку найменшу кількість ходів можна виконати побажання Зеника з Марічкою?

Вхідні дані

У першому рядку задано два цілих числа \(n\) та \(k\) — кількість жеребців на фермі та необхідна кількість жеребців з однаковою масою вівса.

У другому рядку задано \(n\) цілих чисел \(a_i\) — маси вівса в мішках коней.

Вихідні дані

Виведіть ціле число — найменшу кількість ходів.

Обмеження

\(1 \le k \le n \le 2 \cdot 10^5\),

\(1 \le a_i \le 10^9\).

Оцінювання складається з таких блоків:

• по 1 балу за кожен приклад з умови,

• 4 бали: всі \(a_i\) однакові,

• 15 балів: \(n = k\),

• 27 балів: \(a_i \le 2 \cdot 10^3\),

• 13 балів: \(n \le 47, a_i \le 2 \cdot 10^3\),

• 20 балів: \(n \le 2000, a_i \le 2 \cdot 10^5\),

• 19 балів: без додаткових обмежень.

Бали за блок ви отримаєте, тільки якщо ваша програма пройде всі тести з блоку.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
7 4 4 47 74 70 40 7 47	30

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
12 7 8 11 22 36 17 25 1 20 30 81 74 47	41

Примітки

У першому прикладі потрібно за \(23\) ходи забрати \(23\) кг вівса з мішка четвертого коня та за \(7\) ходів додати \(7\) кг вівса до мішка п’ятого коня. Тоді послідовність \(a\) перетвориться на \((4, \underline{47}, 74, \underline{47}, \underline{47}, 7, \underline{47})\). Після всіх \(30\) ходів четверо коней матимуть по \(47\) кг вівса.