Remember-Remainder

dhruba_1603088 BSMRSTU Practice contest...
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

Submit

Login to submit.

Statistics

66% Solution Ratio
agtxdyEarliest, Jan '20
TurinhstuFastest, 0.0s
Shaad221BLightest, 524 kB
omar24Shortest, 493B
Toph uses cookies. By continuing you agree to our Cookie Policy.