410557: GYM104049 I Meteoric Sword

Pure meteoric iron (or star iron) is one of the rarest metals in the universe, and crafting tools out of it is a ludicrous business that requires a lifetime of training. In fact, only 11 people in the universe are trained to forge star iron.

Bob from Sandy Springs, GA is one such tradesman, and he has recently received an order for $$$K$$$ meteoric swords. Because of how valuable meteoric iron is, each sword he sells must be identical (made from the same amount of meteoric iron), so people don't fight over which sword they get.

Bob has $$$N$$$ pre-crafted swords. In one operation, he can take any sword and either add a unit of meteoric iron to it, or remove a unit of meteoric iron.

Can you help Bob solve this problem: given that he needs to sell $$$K$$$ swords, what's the minimum number of operations he needs to perform so that some set of $$$K$$$ swords contain the same amount of meteoric iron?

The first line contains two integers $$$N$$$ and $$$K$$$ ($$$1 \le N \le 10^5$$$, $$$1 \le K \le N$$$), representing the number of total swords and the number of swords Bob needs to sell, respectively.

The second line contains $$$N$$$ integers $$$a_1,...,a_N$$$ ($$$1 \le a_i \le 10^9$$$), representing the amount of meteoric iron currently contained in each sword.

Output a single integer, the minimum number of operations Bob needs to perform so that some set of $$$K$$$ swords all contain the same amount of meteoric iron.

6 3
8 1 2 5 9 3

2

In the example, we can select swords 2, 3, and 6 ([8, 1, 2, 5, 9, 3]). Then if we add 1 unit of iron to the 2nd sword and remove 1 unit of iron from the 6th sword (so that all 3 swords have 2 units of iron), we have performed 2 total operations. It can be shown that this is the minimum number of operations possible.