Aesthetic Text Decomposition

Given a text consisting of n words numbered from 1 to n, each with a certain length, you are to decompose the text into one or more lines. A decomposition is defined by a sequence of numbers \( (a_1,a_2,\ldots,a_{k-1}) \) that indicates that:

• Words 1 to \(a_1\) are in the 1st line,
• Words \(a_1+1\) to \(a_2\) are in the 2nd line,
• \(\vdots\)
• Words \(a_{k-1}+1\) to \(n\) are in the \(k\)th line.

The length of a line that contains words indexed from \(i\) to \(j\) is defined as:

[ \text{line length} = \sum_{p=i}^{j} \text{length}(p) + (j-i) ]

Here, \((j-i)\) is the total width of spaces inserted between adjacent words (each space has width 1).

The coefficient of aestheticism of a decomposition into \(k\) lines is defined as:

[ \sum_{w=1}^{k-1} \left|\text{line}(w) - \text{line}(w+1)\right| ]

If the decomposition has only one line, its coefficient is defined as 0.

There is also a given constant \(m\). Only those decompositions are allowed in which no line has a length greater than \(m\). Among all allowed decompositions (decompositions into any number of lines), you are to find one with the smallest coefficient of aestheticism and output that minimum coefficient.

Note: If no valid decomposition exists, output -1.

inputFormat

The first line of input contains two integers \(m\) and \(n\) (the maximum allowed line length and the number of words, respectively).

The second line contains \(n\) positive integers where the \(i\)th integer denotes the length (number of characters) of word \(i\).

It is guaranteed that \(1 \leq n \leq 100\) and each word length is at most \(100\). \(m\) is a positive integer.

outputFormat

Output a single integer — the minimum coefficient of aestheticism among all valid decompositions. If no valid decomposition exists, output -1.

sample

6 4
4 3 2 5

3