Bags of oats

Limits: 2 sec., 512 MiB

This statement was translated automatically from Ukrainian.

Zenyk and Marichka have \(n\) stallions on their farm, numbered from \(1\) to \(n\). Near each horse, there is its own bag of oats. The bag of the \(i\)-th horse contains \(a_i\) kg of oats.

In one move, you can perform one of two actions:

• add one kilogram of oats to any horse’s bag,

• take one kilogram of oats from any horse’s bag.

Zenyk and Marichka want to be able to find \(k\) stallions on the farm that have the same mass of oats in their bags.

What is the minimum number of moves required to fulfill Zenyk and Marichka’s wish?

Input

The first line gives two integers \(n\) and \(k\) — the number of stallions on the farm and the required number of stallions with the same mass of oats.

The second line gives \(n\) integers \(a_i\) — the masses of oats in the horses’ bags.

Output

Print an integer — the minimum number of moves.

Constraints

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

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

Grading consists of the following blocks:

• 1 point for each example from the statement,

• 4 points: all \(a_i\) are equal,

• 15 points: \(n = k\),

• 27 points: \(a_i \le 2 \cdot 10^3\),

• 13 points: \(n \le 47, a_i \le 2 \cdot 10^3\),

• 20 points: \(n \le 2000, a_i \le 2 \cdot 10^5\),

• 19 points: no additional constraints.

You will receive the points for a block only if your program passes all tests in that block.

Samples

Input (stdin) сopy	Output (stdout) сopy
7 4 4 47 74 70 40 7 47	30

Input (stdin) сopy	Output (stdout) сopy
12 7 8 11 22 36 17 25 1 20 30 81 74 47	41

Notes

In the first example, you need to take \(23\) kg of oats from the fourth horse’s bag in \(23\) moves and add \(7\) kg of oats to the fifth horse’s bag in \(7\) moves. Then the sequence \(a\) will turn into \((4, \underline{47}, 74, \underline{47}, \underline{47}, 7, \underline{47})\). After all \(30\) moves, four horses will have \(47\) kg of oats each.