Вася — начинающий художник. Поскольку опыта у него немного, сейчас он практикуется в рисовании гармоничных полосок.
Каждая полоска, рисуемая Васей, состоит из $$$n$$$ последовательных ячеек, каждая из которых может быть покрашена в один из $$$m$$$ цветов. Яркостью полоски в таком случае называется сумма модулей разностей цветов соседних ячеек. Например, яркость полоски $$$\{3, 1, 5, 2\}$$$ равна $$$|3-1| + |1-5|+|5-2|=9$$$, а яркость полоски $$$\{1, 1, 2\}$$$ равна $$$|1-1|+|1-2|=1$$$.
Как у любого художника, у Васи очень сильно развито чувство прекрасного, и оно подсказывает ему, что полоска будет тем красивее, чем меньше будет её значение яркости. На текущий момент краски цвета $$$i$$$, имеющейся у Васи, хватит для того, чтобы покрасить не более $$$a_i$$$ ячеек. Помогите художнику — определите, какую минимальную яркость может иметь полоска, нарисованная Васей.
В первой строке содержится число $$$n$$$ ($$$1 \leq n \leq 10^9$$$) — размер полоски.
Во второй строке содержится число $$$m$$$ ($$$1 \leq m \leq 3 \cdot 10^5$$$) — количество доступных Васе цветов.
В $$$i$$$-й из следующих $$$m$$$ строк содержится число $$$a_i$$$ ($$$0 \leq a_i \leq 10^9$$$) — количество ячеек, на покраску которых хватит краски цвета $$$i$$$, имеющейся у Васи.
Гарантируется, что $$$n \leq a_1+\dots+a_m$$$ (т.е. Васе хватит краски, чтобы раскрасить все ячейки).
В единственной строке выведите одно число — минимальную яркость, которую может иметь полоска, нарисованная Васей.
Решения, правильно работающие при $$$m \leq 3$$$, будут оцениваться в 20 баллов.
Решения, правильно работающие при $$$n, m \leq 6$$$, будут оцениваться в 25 баллов.
Решения, правильно работающие при $$$m \leq 100$$$, будут оцениваться в 60 баллов.
Решения, правильно работающие при $$$m \leq 1500$$$, будут оцениваться в 70 баллов.
7502311
3
63143
1
