题目描述

Let us consider a text consisting of n words numbered from 1 to n. We represent any of its decompositions into k lines by a sequence of numbers (a_1,a_2...a_{k-1}), such that the words with numbers from 1 to a_1 are in the first line, the words with umbers from a_1 + 1 to a_2 are in the second line, and so on, and finally, the words with numbers from a_{k-1} + 1 to n are in the last, k-th line.

Each word has a certain length (measured in the number of characters). Let length(x) denote the length of the word no. . Furthermore, every two subsequent words in a line are separated by a space of width of a single character. By length of the line we denote the sum of lengths of the words in this line, increased by the number of spaces between them. Let line(w) denote the length of the line no.w . I.e., if the line no.w contains the words with numbers from i to j inclusive, its length is:

XXXX (1st line)
XXX XX (2nd line)
XXXXX (3rd line)

line(w)=length(i)+..length(j)+(j-i)

As an example, let us consider a text consisting of 4 words of lengths 4, 3, 2 and 5, respectively, and its decomposition (1,3) into 3 lines. Then the length of the first line is 4, second -6 , and third -5 :

We shall refer to the number

|line(1)-line(2)|+...+|line(k-1)-line(k)|

as the coefficient of aestheticism of a decomposition of the given text into k lines. Particularly, if the decomposition has only one line, its coefficient of aestheticism is 0.

Needles to say, the smaller the coefficient, the more aesthetical the decomposition. We shall consider only these decompositions that have no line whose length exceeds some constant m. Of all such decompositions of a given text into any number of lines we seek the one most aesthetical, i.e. the one with the smallest coefficient of aestheticism. The aforementioned examplary decomposition's coefficient is 3, and that is exactly the minimum coefficient of aestheticism for m=6 and m=7.

输入格式

The first line of the standard input contains the numbers $m$ and $n$, $1\le m\le 1\ 000\ 000$,$1\le n\le 2\ 000$, separated by a single space. The second, last line of the standard input contains $n$ integers, denotingthe lengths of subsequent words, $1\le length(i)\le m$ for $i=1,2,\cdots,n$, separated by single spaces.

输出格式

The first and only line of the standard output should contain exactly one integer: the minimumcoefficient of aestheticism for those decompositions, whose every line's length does not exceed $m$.

题目大意

       现在, 我们有一个由$n$个单词组成的英文文本. 但是它们都挤在一行里, 单词间以一个半角空格分隔, 就像丑陋的压行代码. 你可以把他们通过$k-1$次换行分割成$k$行的文本并去除行首行末空格. 为方便题意表述, 我们以一个长度为$k-1$的数列$\{a_1,a_2,...,a_{k-1}\}$, 表示第$1$到第$a_1$个单词放在第$1$行, 第$a_1+1$到第$a_2$个单词放在第$2$行, 以此类推.
       不过, 为了让新的文本更加美妙, 你希望在满足每一行的长度不大于$m$的情况下相邻行长度之差的和最小. 具体地, 令$length(i)$表示第$i$个单词的长度, $line(i)$表示第$i$行的长度, 则:

$$line(i)=(a_i-a_{i-1}-1)+\sum_{j=a_{i-1}+1}^{a_i}length(j) $$

你需要求得的答案$Ans$为:

$$Ans=\min_{k,line(i)\le m}\{\sum_{i=1}^{k-1}|line(i)-line(i+1)|\} $$

现在输入单词数$n$, 行长度限制$m$, 每个单词的长度$length(i)$, 请输出答案.

6 4
4 3 2 5

3