Для множества $S$ мы можем отсортировать все его элементы по возрастанию. Разностью множества мы называем максимальную разность между двумя соседними элементами в отсортированном списке.

У вас есть $Q$ множеств неотрицательных целых чисел, разность каждого из которых не превышает $K$. Известно, что минимальный элемент каждого множества равен $0$, а максимальный — $N+1$.

Даны результаты взятия по модулю $M$ количества вхождений каждого элемента от $1$ до $N$ во все $Q$ множеств. Найдите минимальное возможное значение $Q$, удовлетворяющее этим условиям. Если решения не существует, выведите -1.

Входные данные

Первая строка содержит три целых числа $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$.

Для 100% данных: $1 \leq N \leq 500000, 1 \leq K \leq N, 2 \leq M \leq 10^9$.