考虑一个由 $n$ 个单词组成的文本，单词编号从 $1$ 到 $n$。我们将该文本划分为 $k$ 行的方案表示为一个数字序列 $(a_1, a_2, \dots, a_{k-1})$，其中第 $1$ 到 $a_1$ 号单词在第一行，第 $a_1+1$ 到 $a_2$ 号单词在第二行，以此类推，最后第 $a_{k-1}+1$ 到 $n$ 号单词在第 $k$ 行。

每个单词都有一定的长度（以字符数计）。令 $\text{length}(x)$ 表示第 $x$ 个单词的长度。此外，同一行中每两个相邻单词之间由一个字符宽度的空格隔开。行的长度定义为该行所有单词长度之和加上单词之间的空格数。令 $\text{line}(w)$ 表示第 $w$ 行的长度。即，如果第 $w$ 行包含从第 $i$ 到第 $j$ 号单词（包含 $i$ 和 $j$），则其长度为：

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

例如，考虑一个由 4 个单词组成的文本，长度分别为 4, 3, 2 和 5，将其划分为 3 行的方案为 (1, 3)。此时第一行的长度为 4，第二行为 6，第三行为 5：

我们将数值

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

称为该文本划分为 $k$ 行方案的“美观系数”。特别地，如果划分只有一行，其美观系数为 0。

显然，系数越小，划分越美观。我们只考虑那些没有任何一行长度超过常数 $m$ 的划分。在所有满足条件的划分中，我们寻找最美观的一种，即美观系数最小的一种。上述示例划分的美观系数为 3，这正是当 $m=6$ 和 $m=7$ 时的最小美观系数。

编写一个程序：

• 从标准输入读取数字 $m$ 和 $n$ 以及各单词的长度，
• 确定满足每一行长度均不超过 $m$ 的所有划分中的最小美观系数，
• 将结果输出到标准输出。

输入格式

标准输入的第一行包含数字 $m$ 和 $n$，$1 \le m \le 1\,000\,000$，$1 \le n \le 2\,000$，由单个空格分隔。标准输入的第二行（最后一行）包含 $n$ 个整数，表示后续单词的长度，$1 \le \text{length}(i) \le m$（对于 $i=1, 2, \dots, n$），由单个空格分隔。

输出格式

标准输出的第一行且仅包含一行，应包含一个整数：满足每一行长度均不超过 $m$ 的所有划分中的最小美观系数。

样例

输入 1

6 4
4 3 2 5

输出 1

3

输入 2

4 2
1 2

输出 2

0