I. Хрустальные шары
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В мире Compfestnesia Пак Чанек нашел секретное подземелье. Внутри него находится сундук с сокровищами, окруженный $$$n$$$ статуями, расположенными по кругу. Статуи пронумерованы от $$$0$$$ до $$$n-1$$$, причем статуя $$$i$$$ находится слева от статуи $$$i+1$$$, а статуя $$$n-1$$$ — слева от статуи $$$0$$$.

Пак Чанек заметил, что каждая статуя держит хрустальный шар с целым числом от $$$0$$$ до $$$m-1$$$ включительно. В хрустальном шаре статуи $$$i$$$ содержится число $$$a_i$$$.

В подземелье есть инструкция, согласно которой, чтобы открыть сундук с сокровищами, все целые числа в хрустальных шарах должны быть равны $$$0$$$. Для этого Паку Чанеку дается целое число $$$k$$$, и он может выполнить ноль или более операций. За одну операцию Пак Чанек делает следующее:

  1. Он выберет ровно $$$k$$$ последовательных статуй. Другими словами, выберет статуи $$$p, (p+1) \bmod n, (p+2) \bmod n, (p+3) \bmod n, \ldots, (p+k-1) \bmod n$$$ для некоторого выбранного индекса $$$p$$$.
  2. Выполнит одно из следующих действий:
    • Для каждой выбранной статуи заменит её значение $$$a_i$$$ на $$$(a_i+1) \bmod m$$$.
    • Для каждой выбранной статуи заменит её значение $$$a_i$$$ на $$$(a_i-1) \bmod m$$$.

Помогите Паку Чанеку найти минимально возможное количество операций, чтобы открыть сундук с сокровищами.

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

Первая строка содержит три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$2 \leq n,m \leq 10^6$$$, $$$nm \leq 2 \cdot 10^6$$$, $$$1 \leq k < n$$$) — количество статуй, верхнее ограничение на значения чисел в хрустальных шарах и количество статуй, которые можно изменять за одну операцию.

Вторая строка содержит $$$n$$$ целых чисел $$$a_0,a_1,\ldots,a_{n-1}$$$ ($$$0 \leq a_i < m$$$) — целые числа в хрустальных шарах.

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

Если возможно выполнить ноль или более операций так, чтобы стало $$$a_0=a_1=\ldots=a_{n-1}=0$$$, выведите минимальное требуемое количество операций. В противном случае выведите $$$-1$$$.

Примеры
Входные данные
5 9 3
8 1 4 5 0
Выходные данные
7
Входные данные
4 4 2
1 0 0 0
Выходные данные
-1
Входные данные
5 5 2
1 0 0 0 0
Выходные данные
10
Примечание

В первом примере Пак Чанек может выполнять следующие операции:

  1. Выполнить операцию $$$a_i := (a_i-1) \bmod m$$$ $$$3$$$ раза для статуй $$$1$$$, $$$2$$$ и $$$3$$$. Теперь $$$a=[8,7,1,2,0]$$$.
  2. Выполнить операцию $$$a_i := (a_i-1) \bmod m$$$ $$$1$$$ раз для статуй $$$3$$$, $$$4$$$ и $$$0$$$. Теперь $$$a=[7,7,1,1,8]$$$.
  3. Выполнить операцию $$$a_i := (a_i+1) \bmod m$$$ $$$2$$$ раза для статуй $$$4$$$, $$$0$$$ и $$$1$$$. Теперь $$$a=[0,0,1,1,1]$$$.
  4. Выполнить операцию $$$a_i := (a_i-1) \bmod m$$$ $$$1$$$ раз для статуй $$$2$$$, $$$3$$$ и $$$4$$$. Теперь $$$a=[0,0,0,0,0]$$$.