5. Sense of Beauty
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Peter is a beginner artist. Since he has little experience, he is currently practicing drawing harmonious stripes.

Each stripe drawn by Peter consists of $$$n$$$ consecutive cells, each of which can be painted in one of $$$m$$$ colors. The brightness of a stripe is defined as the sum of the absolute differences between the colors of adjacent cells. For example, the brightness of the stripe $$$\{3, 1, 5, 2\}$$$ is $$$|3-1| + |1-5| + |5-2| = 9$$$, and the brightness of the stripe $$$\{1, 1, 2\}$$$ is $$$|1-1| + |1-2| = 1$$$.

Like any artist, Peter has a very strong sense of beauty, and it tells him that the stripe will be more beautiful the smaller its brightness is. At the moment, the paint of color $$$i$$$ that Peter has is enough to paint no more than $$$a_i$$$ cells. Help the artist — determine the minimum brightness that a stripe drawn by Peter can have.

Input

The first line contains the number $$$n$$$ ($$$1 \leq n \leq 10^9$$$) — the length of the stripe.

The second line contains the number $$$m$$$ ($$$1 \leq m \leq 3 \cdot 10^5$$$) — the number of colors available to Peter.

The $$$i$$$-th of the following $$$m$$$ lines contains the number $$$a_i$$$ ($$$0 \leq a_i \leq 10^9$$$) — the number of cells that can be painted with the paint of color $$$i$$$ that Peter has.

It is guaranteed that $$$n \leq a_1+\dots+a_m$$$ (i.e. Peter has enough paint to color all cells).

Output

Print a single number — the minimum brightness that a stripe drawn by Peter can have.

Scoring

Solutions that work correctly for $$$m \leq 3$$$ will be awarded 20 points.

Solutions that work correctly for $$$n, m \leq 6$$$ will be awarded 25 points.

Solutions that work correctly for $$$m \leq 100$$$ will be awarded 60 points.

Solutions that work correctly for $$$m \leq 1500$$$ will be awarded 70 points.

Examples
Input
7
5
0
2
3
1
1
Output
3
Input
6
3
1
4
3
Output
1