對於一個集合 $S$，我們可以將其中所有元素由小到大排序，我們定義這個集合的差異值為排序後相鄰兩個數的差的最大值。

你有 $Q$ 個差異值不超過 $K$ 的非負整數集合，已知每個集合中的最小元素為 $0$，最大元素為 $N+1$。

現在已知 $1$ 到 $N$ 每個元素在 $Q$ 個集合中的出現次數對 $M$ 取模的結果，求在滿足條件的情況下，$Q$ 的最小值是多少。若無解，請輸出 -1。

輸入格式

第一行包含三個整數 $N, K, M$。 接下來一行包含 $N$ 個整數，第 $i$ 個整數表示第 $i$ 個元素的出現次數對 $M$ 取模的結果。

輸出格式

輸出一個整數，表示 $Q$ 的最小值；若無解，則輸出 -1。

範例

範例輸入 1

3 2 8
0 0 1

範例輸出 1

8

範例輸入 2

3 1 9
2 3 3

範例輸出 2

-1

資料範圍

對於 10% 的資料，$K = 1$。

對於另外 10% 的資料，$K = 2$ 且 $N = 5$。

對於另外 20% 的資料，$K = 2$ 且 $N \leq 50$。

對於另外 15% 的資料，保證答案小於 $M$，且 $N \leq 50$。

對於另外 25% 的資料，$N \leq 20$。

對於 100% 的資料，$1 \leq N \leq 500000, 1 \leq K \leq N, 2 \leq M \leq 10^9$。