STC09 - Aesthetic Text

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 (a1, a2, a3 ... ak-1), such that the words with numbers from 1 to a1 are in the first line, the words with numbers from a1+1 to a2 are in the second line, and so on, and finally, the words with numbers from aK-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 number x. Furthermore, every two adjacent 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 number w. I.e., if the line number w contains the words with numbers from i to j inclusive, its length is:

line(w) = length(i) + length(i+1) + ... + 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 is 6, and third is 5:

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

We shall refer to the number

|line(1) - line(2)| + |line(2) - line(3)| + ... + |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.

Needless 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 exemplary decomposition's coefficient is 3, and that is exactly the minimum coefficient of aestheticism for M = 6 and M = 7.

Task

Write a program that:

  • reads from the standard input the numbers M and N, and the lengths of the words,
  • determines the minimum coefficient of aestheticism for those decompositions, whose every line is of length not exceeding M,
  • writes the result to the standard output.

Input

The first line of the standard input contains the numbers M and N, (1 <= M <= 1000000, 1 <= N <= 2000) separated by a single space. The second, last line of the standard input contains N integers, denoting the lengths of subsequent words, 1 <= length(i) <= N for i = 1, 2, 3 ... N, separated by single spaces.

Output

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

Example

For the input data:

6 4
4 3 2 5

the correct result is:

3

while for the following input data:

4 2
1 2

the correct result is:

0

Added by:Sergey Kulik
Date:2013-08-06
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:POI XIII

hide comments
2023-09-24 00:08:31 Oleg
Current clusters are too fast. O(N^3) passes.
2013-11-02 08:06:25 Jacob Plachta
As in the samples, M comes before N on the first line.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.