For a set $S$, we can sort all its elements in ascending order. We define the difference value of this set as the maximum difference between adjacent elements after sorting.

You are given $Q$ sets of non-negative integers, each with a difference value not exceeding $K$. It is known that for each set, the minimum element is $0$ and the maximum element is $N+1$.

You are given the number of occurrences of each element from $1$ to $N$ across the $Q$ sets, modulo $M$. Find the minimum possible value of $Q$ that satisfies these conditions. If no solution exists, output $-1$.

Input

The first line contains three integers $N$, $K$, and $M$. The next line contains $N$ integers, where the $i$-th integer represents the number of occurrences of the $i$-th element modulo $M$.

Output

Output a single integer representing the minimum value of $Q$. If no solution exists, output $-1$.

Examples

Input 1

3 2 8
0 0 1

Output 1

8

Input 2

3 1 9
2 3 3

Output 2

-1

Constraints

• For 10% of the data, $K = 1$.
• For another 10% of the data, $K = 2$ and $N = 5$.
• For another 20% of the data, $K = 2$ and $N \leq 50$.
• For another 15% of the data, the answer is guaranteed to be less than $M$, and $N \leq 50$.
• For another 25% of the data, $N \leq 20$.
• For 100% of the data, $1 \leq N \leq 500000$, $1 \leq K \leq N$, $2 \leq M \leq 10^9$.