균형 잡힌 텍스트

$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$번째 줄에 놓인다.

각 단어는 (문자 개수로 측정한) 길이를 가진다. $length(x)$를 $x$번 단어의 길이라고 하자. 또한 한 줄 안에서 이웃한 두 단어는 폭이 문자 하나인 공백으로 구분된다. 어떤 줄의 길이는 그 줄에 있는 단어 길이의 합에 단어 사이 공백의 개수를 더한 값으로 정의한다. $w$번째 줄의 길이를 $line(w)$라고 하자. 즉, $w$번째 줄이 $i$번부터 $j$번까지의 단어를 담고 있다면 그 길이는 다음과 같다.

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

다음 값을

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

이 분할의 미적 계수라고 부른다. 특히 줄이 하나뿐인 분할의 미적 계수는 $0$이다.

당연히 계수가 작을수록 더 균형 잡힌 분할이다. 우리는 어떤 줄의 길이도 정해진 상수 $m$을 넘지 않는 분할만 고려한다. 주어진 텍스트를 임의의 줄 수로 나눈 그런 모든 분할 중에서 가장 균형 잡힌 것, 즉 미적 계수가 가장 작은 것을 찾는다.

예를 들어 길이가 각각 $4, 3, 2, 5$인 단어 $4$개로 이루어진 텍스트와 이를 $3$줄로 나눈 분할 $(1, 3)$을 생각해 보자. 첫째 줄은 단어 $1$번(길이 $4$), 둘째 줄은 단어 $2$번과 $3$번($3 + 2 + 1 = 6$), 셋째 줄은 단어 $4$번(길이 $5$)을 담는다.

XXXX
XXX XX
XXXXX

이 분할의 미적 계수는 $|4 - 6| + |6 - 5| = 3$이며, 이는 $m = 6$일 때와 $m = 7$일 때의 최소 미적 계수와 정확히 일치한다.

다음을 수행하는 프로그램을 작성하라.

• 표준 입력에서 $m$과 $n$, 그리고 각 단어의 길이를 읽는다.
• 모든 줄의 길이가 $m$을 넘지 않는 분할들에 대한 최소 미적 계수를 구한다.
• 그 결과를 표준 출력에 쓴다.

첫째 줄에 두 정수 $m$과 $n$이 공백 하나로 구분되어 주어진다 ($1 \le m \le 1{,}000{,}000$, $1 \le n \le 2{,}000$). 둘째 줄이자 마지막 줄에는 각 단어의 길이를 나타내는 $n$개의 정수가 공백 하나로 구분되어 주어진다. 모든 $i = 1, 2, \dots, n$에 대해 $1 \le length(i) \le m$이다.

첫째 줄이자 유일한 줄에, 모든 줄의 길이가 $m$을 넘지 않는 분할의 최소 미적 계수를 정수 하나로 출력한다.