Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Remember-Remainder

By dhruba_1603088 · Limits 1s, 256 MB

Zarin is a sadist. She loves to give problems to her close people. Today she gives you an array consisting of n integers a1, a2,…,an, and a positive integer k. She tells you that k is a divisor of n always.

Now you have to do magic.

In a single magic, you can take any index i between 1 and n and increase ai by 1.

Let’s determine xr (0 ≤ r ≤ k − 1) — the number of items consisting remainder r when divided by k. For each remainder, let’s find the number of corresponding items in a with that remainder.

You have to modify the array in a way that x0 = x1 = ⋯ = xk-1 = n/k.

Now Zarin wants to know the minimum number of magics to satisfy the above requirement.

Input

The first line of input contains two integers n and k (1 ≤ n ≤ 2*105,1 ≤ k ≤ n).

The second line of input contains n integers a1,a2,…,an (0 ≤ ai ≤ 109).

Output

Print a single integer — the minimum number of moves required to satisfy the following condition: for each remainder from 0 to k−1, the number of elements of the array having this remainder equals n/k.

Sample

InputOutput
6 3
6 10 12 3 0 2
3

Discussion

Statistics


61% Solution Ratio

agtxdyEarliest, 8M ago

EgorKulikovFastest, 0.0s

Shaad221BLightest, 524 kB

omar24Shortest, 493B

Submit

Login to submit