5. Покраска забора
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Недавно Егор узнал, что средняя зарплата маляра в России составляет более ста тысяч рублей в месяц. Сейчас он получает немного меньше (примерно ноль рублей в месяц), а потому пошел работать маляром.

В первый же день работы он получил свое первое задание — покрасить забор, состоящий из $$$k$$$ досок. Опишем этот процесс немного подробнее. Забор можно представить как $$$k$$$ палок, стоящих в ряд. Слева от забора стоит телега, в которой есть $$$n$$$ банок с красками — при этом $$$i$$$-й банки хватит ровно на $$$a_i$$$ досок.

Изначально Егор стоит слева от забора (прямо перед телегой), при этом в его руке нет банки с краской. Егор пока что не окончил ВУЗ, поэтому набор его способностей ограничен:

  • Взять банку с краской. Если Егор стоит перед телегой, то он может взять в руку любую банку, в которой еще осталась краска. Если у Егора уже была какая-то банка в руке, то он возьмет новую, а старую оставит у телеги. Это действие не занимает времени.
  • Сдвинуться вправо. После этого Егор перейдет к следующей доске. Если Егор стоял у телеги, то после этого перемещения он будет стоять перед первой доской. При этом Егор не может сдвинуться вправо, если он уже у последней доски. Это действие занимает $$$1$$$ секунду.
  • Сдвинуться влево. После этого Егор перейдет к предыдущей доске. Если Егор стоит у первой доски, то после этого перемещения он будет стоять перед телегой. Конечно же, Егор не может сдвинуться влево, если он стоит перед телегой. Это действие занимает $$$1$$$ секунду.
  • Покрасить доску. Если Егор сейчас стоит перед непокрашенной доской, а также у него в руках есть банка с краской, то он может покрасить эту доску. Это действие занимает $$$1$$$ секунду.

Раньше Егор был пасечником, а потому ему не понаслышке известна фраза «Время — деньги!». Соответственно, он хочет как можно быстрее покрасить весь забор. Вы ведь помните, что Егор не окончил ВУЗ? Именно поэтому вам придется посчитать, какое минимальное время потребуется на покраску всего забора. Обратите внимание на то что Егор имеет право закончить покраску в любом месте забора, а также ему не надо после этого возвращаться к телеге.

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

В первой строке дано целое число $$$k$$$ ($$$1 \le k \le 10^9$$$) — количество досок в заборе.

Во второй строке дано целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество банок в телеге.

В следующих $$$n$$$ строках даны целые числа $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$) — на сколько досок хватит краски в банке с номером $$$i$$$.

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

Если Егору не хватит краски для выполнения своего задания, то выведите «-1» (без кавычек). Иначе выведите минимальное количество секунд, которое потребуется Егору для покраски всего забора.

Примеры
Входные данные
5
3
1
3
2
Выходные данные
14
Входные данные
100
1
1
Выходные данные
-1
Входные данные
6
3
5
5
5
Выходные данные
14
Примечание

Рассмотрим первый пример. В заборе есть всего пять досок. Чтобы покрасить его как можно быстрее, Егору нужно сначала взять третью банку, потом покрасить первые две доски — на это у него уйдет $$$4$$$ секунды. Затем он должен вернуться назад и взять банку, которой хватит на три доски, — на это еще $$$2$$$ секунды. Затем надо докрасить забор — на это уйдет еще $$$8$$$ секунд, первые две из которых он будет идти рядом с уже покрашенными досками. Итого потребуется $$$4 + 2 + 8 = 14$$$ секунд.

Во втором примере у Егора есть возможность покрасить только одну доску, но этого не хватит на покраску всего забора.