22 1 s 128 MB
We have a paragraph of text to print. A text is a sequence of words and each word consists of characters. When we print a text, we print the words from the text one at a time, according to the order the words appear in the text. The words are printed in lines, and we can print at most M characters in a line. If there is space available, we could print more than one word in a line. However, when we print more than one word in a line, we need to place exactly one space character between two adjacent words in a line. For example, when we are given a text like the following:
This is a text of fourteen words and the longest word has ten characters
Now we can print this text into lines of no more than 20 characters as the following.
a text of
and the longest
has ten characters
The first line of the input is the number of test cases (C). The first line of a test case is the maximum number of characters allowed in a line (M). The second line of a test case is the number of words in the text (N). The following N lines are the length (in character) of each word in the text. It is guaranteed that no word will have more than M characters, N is at most 10000, and M is at most 100.
The output has C lines. Each line has the minimum penalty one needs to pay in order to print the text in that test case.
2 20 14 4 2 1 4 2 8 5 3 3 7 4 3 3 10 30 14 4 2 1 4 2 8 5 3 3 7 4 3 3 10