[AdditionalFile5505.zip](file://AdditionalFile5505.zip?type=additional_file)

#5505. 「POI2006 R3」美学的文本 Aesthetic Text

标签: 传统 | 时间限制: 400 ms | 内存限制: 128 MiB |

题目描述

题目译自 XIII OI Olimpiada Informatyczna – III etap Estetyczny tekst

我们来考虑一个由 $n$ 个单词组成的任意文本，这些单词的编号从 $1$ 到 $n$。该文本的任意一个划分为 $k$ 行的方案，都可以用一个数字序列 $(a_1, a_2, \ldots, a_{k-1})$ 来表示。其中，编号从 $1$ 到 $a_1$ 的单词位于第一行，编号从 $a_1+1$ 到 $a_2$ 的单词位于第二行，以此类推，而编号从 $a_{k-1}+1$ 到 $n$ 的单词则位于最后的第 $k$ 行。

每个单词都有一个确定的长度（以字符数表示）。编号为 $x$ 的单词的长度记为 $\operatorname{length}(x)$。此外，同一行中任意两个相邻的单词都由一个字符宽度的空格隔开。一行的长度定义为该行所有单词的长度之和，再加上它们之间的空格数。第 $w$ 行的长度我们记为 $\operatorname{line}(w)$。这意味着，如果第 $w$ 行包含了从编号 $i$ 到 $j$（含两端）的单词，那么这一行的长度为：

$$\operatorname{line}(w)=\operatorname{length}(i)+\operatorname{length}(i+1)+\ldots+\operatorname{length}(j)+(j-i)$$

举个例子，我们来考虑一个由 $4$ 个单词组成的文本，其长度依次为 $4、3、2、5$，并将其通过序列 $(1, 3)$ 划分为 $3$ 行。那么，第一行的长度为 $4$，第二行为 $6$，第三行为 $5$：

$$\text{XXXX}$$ $$\text{XXX XX}$$ $$\text{XXXXX}$$

对于一个将给定文本划分为 $k$ 行的方案，我们将其美学系数定义为由以下公式计算出的数值：

$$|\operatorname{line}(1)-\operatorname{line}(2)|+|\operatorname{line}(2)-\operatorname{line}(3)|+\ldots+|\operatorname{line}(k-1)-\operatorname{line}(k)|$$

特别地，如果整个划分只占一行，其美学系数等于 $0$。

美学系数越小，表示该划分方案越美观。我们只考虑那些任意一行的长度都不超过某个给定常数 $m$ 的划分方案。在所有满足此条件的、将文本划分为任意行数的方案中，我们寻求最美观的划分，即具有最小美学系数的方案。在上面的例子中，该划分的美学系数等于 $3$，并且当 $m=6$ 或 $m=7$ 时，这是美学系数的最小值。

请编写一个程序，实现以下功能：

• 从标准输入读取数字 $m$ 和 $n$ 以及后续各个单词的长度。
• 在所有任意一行长度均不超过 $m$ 的划分方案中，找出最小的美学系数。
• 将结果输出到标准输出。

输入格式

输入的第一行包含两个整数 $m$ 和 $n$ $(1 \le m \le 1000000, 1 \le n \le 2000)$，由单个空格隔开。

输入的第二行也是最后一行，包含 $n$ 个整数，即后续各个单词的长度，对于 $i=1, 2, \ldots, n$，满足 $1 \le \text{length}(i) \le m$，这些数字由单个空格隔开。

输出格式

输出的第一行且仅一行应包含一个整数：在所有任意一行长度均不超过 $m$ 的划分方案中，最小的美学系数。

样例 1

输入

6 4
4 3 2 5

输出

3

样例 2

输入

4 2
1 2

输出

0