A. Ограбление
ограничение по времени на тест
1 second
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

Ночь. Неуловимый Джо пробрался внутрь сейфа главного банка страны. Здесь имеется n ячеек, расположенных в ряд, в каждой из которых лежит некоторое количество алмазов. Для удобства пронумеруем ячейки натуральными числами от 1 до n слева направо.

К сожалению, Джо не отключил последнюю из систем безопасности. Зато он знает как она устроена.

Каждую минуту система безопасности определяет для каждых двух соседних ячеек (разность номеров которых ровно 1) суммарное количество алмазов в них. В итоге получается n - 1 сумма. Если хотя бы одна из них отличается от соответствующей суммы, полученной при предыдущем измерении, система безопасности срабатывает.

Джо может перемещать алмазы между проверками системы безопасности. За минуту между двумя проверками он успевает сделать не более m перемещений. Перемещением считается одна из трех следующих операций: перемещение алмаза из любой ячейки в любую другую, перемещение алмаза из любой ячейки в карман Джо, перемещение алмаза из кармана в любую ячейку. Изначально карман Джо пуст, в любую ячейку и в карман помещается неограниченное количество алмазов. Считается, что до всех действий Джо система делает хотя бы одну проверку.

Утром в банк придут банковские служащие, поэтому Джо должен уйти из банка до этого момента. У Джо есть k перерывов между проверками системы безопасности перед тем, как нужно будет скрыться. Все, что останется при этом у Джо в кармане, считается его добычей.

Определите наибольшее количество алмазов, которые может унести с собой Джо. Система безопасности при этом не должна сработать (в том числе и после того, как Джо покинет банк), а скрыться Джо должен до наступления утра.

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

В первой строке находятся целые числа n, m и k (1 ≤ n ≤ 104, 1 ≤ m, k ≤ 109). В следующей строке находятся n чисел. i-ое из них равно количеству алмазов в i-ой ячейке — целое число от 0 до 105.

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

Выведите одно целое число — максимальное количество алмазов, которые может унести с собой Джо.

Примеры
Входные данные
2 3 1
2 3
Выходные данные
0
Входные данные
3 2 2
4 1 3
Выходные данные
2
Примечание

Во втором примере Джо может действовать следующим образом.

Изначально расположение алмазов 4 1 3.

За первый перерыв Джо перекладывает один алмаз из 1-ой ячейки во 2-ую и один алмаз из 3-ей ячейки себе в карман.

Расположение алмазов в конце первого перерыва 3 2 2. Проверка не находит изменений и система безопасности не срабатывает.

За второй перерыв Джо перекладывает один алмаз из 3-ей ячейки во 2-ую и один алмаз из 1-ой ячейки себе в карман.

Расположение алмазов в конце второго перерыва 2 3 1. Проверка опять не находит изменений и система безопасности не срабатывает.

Теперь Джо уходит с 2 алмазами в кармане.