集合 $S$ の差分値は、 $S$ の要素を昇順に並べたとき、隣接する要素の差の最大値として定義されます。

$Q$ 個の非負整数集合があり、各集合の差分値は $K$ 以下です。各集合において、最小の要素は $0$、最大の要素は $N+1$ であることがわかっています。

$1$ から $N$ までの各要素が $Q$ 個の集合に出現する回数を $M$ で割った余りが与えられます。これらの条件を満たす $Q$ の最小値を求めてください。解が存在しない場合は $-1$ を出力してください。

入力

第一行に3つの整数 $N, K, M$ が与えられます。 続く一行に $N$ 個の整数が与えられ、$i$ 番目の整数は要素 $i$ が $Q$ 個の集合に出現する回数を $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$ である。
• すべてのデータにおいて、$1 \leq N \leq 500000, 1 \leq K \leq N, 2 \leq M \leq 10^9$ である。