[POI2006]Est

一篇文章由 $N$ 个句子按顺序组成，第 $i$ 个句子的长度为 $A_i$。现在要把这篇文章排版成若干行，规则如下：

• 只能把若干个连续的句子放到同一行；
• 同一行中任意相邻两个句子之间用一个空格隔开；
• 每一行的总宽度（该行所有句子的长度之和，加上句子之间的空格数）不能超过 $M$。

一种排版方案的不合谐度定义为相邻两行宽度之差的绝对值之和。例如对于下面这个排版：

XXXX
XXX XX
XXXXX

三行的宽度依次为 $4, 6, 5$，因此它的不合谐度为

$$|6-4|+|5-6|=3.$$

如果文章只有一行，则不合谐度为 $0$。

你的任务是进行排版操作，使文章的不合谐度最小。

输入格式

第一行两个整数 $M, N$，分别表示每行总宽度的上限和句子的数目。

第二行 $N$ 个整数，第 $i$ 个数为 $A_i$，表示第 $i$ 个句子的长度。

输出格式

输出一行一个整数，表示最小的不合谐度。

样例输入

6 4
4 3 2 5

样例输出

3

样例解释

四个句子的长度依次为 $4, 3, 2, 5$，每行宽度不能超过 $6$。把它们排成

XXXX
XXX XX
XXXXX

即第一行放第 $1$ 个句子，第二行放第 $2, 3$ 个句子，第三行放第 $4$ 个句子，三行宽度依次为 $4$、$3+1+2=6$、$5$，不合谐度为 $|6-4|+|5-6|=3$。

数据范围

• $1\le M\le 10^6$；
• $1\le N\le 2000$；
• $1\le A_i\le M$。

来源与许可

本题为 POI 2006 试题「Est」，题面与测试数据整理自 BZOJ 1521。

样例 1

输入

6 4
4 3 2 5

输出

3