对于一个集合 $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$