Problem Statement

There are $N$ cakes, and the size of the $i$-th cake is $A_i$. You are going to distribute these cakes to $M$ people.

Let $S$ be the total size of the cakes, $A_1+\dots+A_N$. Here, it is guaranteed that $S$ is a multiple of $M$.

You can perform the following operation any number of times (possibly zero) in any order.

• Choose one cake and cut it into $2$ pieces in any way you like (the sizes need not be integers).

After the operations, you distribute the cakes to the $M$ people. Find the minimum number of operations required so that the total size of the cakes each person receives is $\frac{S}{M}$.

A more formal statement is as follows.

• You are given a sequence $A=(A_1,\dots,A_N)$ and a positive integer $M$. Let $S=\sum_i A_i$.
• You can perform the following operation any number of times.
• Choose an integer $i$ with $1\leq i \leq |A|$ and a real number $x$ with $0 < x < A_i$. Replace $A$ with the sequence of length $|A|+1$ obtained by appending $x,A_i-x$ to the end of $A$ and removing the $i$-th element.
• Find the minimum number of operations required for there to exist a $\mathcal{P}$ satisfying all of the following conditions.
• $\mathcal{P}$ is a partition of $\{1,2,\dots,|A|\}$; that is, it is a set satisfying the following $3$ conditions.
  • Each element of $\mathcal{P}$ is a subset of $\{1,2,\dots,|A|\}$.
    • If $X,Y \in \mathcal{P}$ and $X\neq Y$, then $X \cap Y = \emptyset$.
    • $\bigcup_{X \in \mathcal{P}}X=\{1,2,\dots,|A|\}$ holds.
  • $\sum_{i\in X}A_i=\frac{S}{M}$ holds for every $X\in \mathcal{P}$.

Constraints

• $1 \leq N \leq 20$
• $1 \leq M \leq 100$
• $1 \leq A_i \leq 10^9$
• $A_1+\dots+A_N$ is a multiple of $M$.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
A_1 A_2 \dots A_N

Output

Print the answer.