Aesthetic Text

Consider a text consisting of $n$ words numbered from $1$ to $n$. Any decomposition of the text into $k$ lines is represented by a sequence $(a_1, a_2, \dots, a_{k-1})$: the words numbered $1$ through $a_1$ go on the first line, the words numbered $a_1 + 1$ through $a_2$ go on the second line, and so on, and finally the words numbered $a_{k-1} + 1$ through $n$ go on the last, $k$-th line.

Each word has a certain length, measured in characters. Let $length(x)$ denote the length of word number $x$. Within a line, every two neighboring words are separated by a space one character wide. The length of a line is defined as the sum of the lengths of the words on it, increased by the number of spaces between them. Let $line(w)$ denote the length of the $w$-th line. That is, if the $w$-th line contains the words numbered from $i$ to $j$ inclusive, its length is

$line(w) = length(i) + length(i+1) + \dots + length(j) + (j - i)$

We call the value

$|line(1) - line(2)| + |line(2) - line(3)| + \dots + |line(k-1) - line(k)|$

the coefficient of aestheticism of the decomposition. In particular, a decomposition with a single line has coefficient $0$.

Naturally, the smaller the coefficient, the more aesthetic the decomposition. We consider only decompositions in which no line is longer than a fixed constant $m$. Among all such decompositions of the text into any number of lines, we seek the most aesthetic one, that is, the one with the smallest coefficient of aestheticism.

For example, consider a text of $4$ words with lengths $4, 3, 2, 5$ and its decomposition $(1, 3)$ into $3$ lines. The first line holds word $1$ (length $4$), the second holds words $2$ and $3$ ($3 + 2 + 1 = 6$), and the third holds word $4$ (length $5$):

XXXX
XXX XX
XXXXX

The coefficient of this decomposition is $|4 - 6| + |6 - 5| = 3$, which is exactly the smallest coefficient of aestheticism for both $m = 6$ and $m = 7$.

Write a program that:

• reads $m$, $n$, and the lengths of the words from standard input,
• determines the smallest coefficient of aestheticism over the decompositions in which every line has length at most $m$,
• writes the result to standard output.

The first line contains two integers $m$ and $n$ separated by a single space ($1 \le m \le 1{,}000{,}000$, $1 \le n \le 2{,}000$). The second and last line contains $n$ integers, the lengths of the successive words, separated by single spaces, with $1 \le length(i) \le m$ for every $i = 1, 2, \dots, n$.

The first and only line of standard output should contain exactly one integer: the smallest coefficient of aestheticism over the decompositions in which no line has length greater than $m$.