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

Обмеження: 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$ кг вівса.