Transformation to Power of Two Multiples

Little Ming loves powers of two. He has an array of n positive integers \(a_1, a_2, \dots, a_n\). He can perform the following operation any number of times (possibly 0): choose an index \(i\) and add any positive integer \(d\) to \(a_i\), with the restriction that \(a_i + d \le 10^5\).

After all the operations, he wants the product \(\prod_{i=1}^{n}a_i\) to be divisible by \(2^k\) (i.e. to have at least \(k\) factors of 2 in its prime factorization). Determine the minimum total sum of \(d\) added over all operations so that this goal is achieved.

Note: For any positive integer \(x\), let \(v_2(x)\) denote the exponent of 2 in its prime factorization. The final requirement is equivalently:

[ \sum_{i=1}^{n}v_2(a_i + d_i) \ge k, ]

where each \(a_i + d_i \le 10^5\) and each \(d_i\) is a nonnegative integer (with \(d_i = 0\) meaning no change).

inputFormat

The first line contains two integers \(n\) and \(k\) \((1 \le n \le 10^5,\; 1 \le k \le 10^5)\).

The second line contains \(n\) positive integers \(a_1, a_2, \dots, a_n\) \((1 \le a_i \le 10^5)\).

outputFormat

Output a single integer -- the minimum total sum of numbers added to the array so that \(\prod_{i=1}^{n}(a_i+d_i)\) is divisible by \(2^k\). It is guaranteed that under the given constraints there is always a solution.

sample

3 3
2 3 5

1