Problem Statement

You are given an integer sequence $A=(A_1,A_2,\cdots,A_N)$ of length $N$. Each element of $A$ is an integer between $0$ and $N-1$, inclusive.

You can perform the following operation zero or more times:

• Choose exactly $M$ elements from $A$. Then, increase the value of each chosen element by $1$. Now, if some elements have the values of $N$, change those values to $0$.

Your goal is to make $A$ a permutation of $(0,1,\cdots,N-1)$. Determine if the goal is achievable. If it is, find the minimum number of operations required.

Constraints

• $2 \leq N \leq 250000$
• $1 \leq M \leq N-1$
• $0 \leq A_i \leq N-1$
• All input values are integers.

Input

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

N M
A_1 A_2 \cdots A_N

Output

If the goal is unachievable, print $-1$. Otherwise, print the minimum number of operations required.