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.
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).
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.
Input | Output |
---|---|
6 3 6 10 12 3 0 2 | 3 |