1649. Print Words in Lines

单点时限: 2.0 sec

内存限制: 256 MB

We have a pragraph 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 weo 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.

This is

a text of

fourteen words

and the longest

word

has ten characters

However, when you print less than 20 characters in a line you need to pay a penalty, which is equal to the square of the difference between 20 and the actual number of characters you printed in that line.For example in the first line we actually printed seven characters so the penalty is (20-7)^2=169.The total penalty is the sum of all penalties from all lines. Given the text and the number of maximum number of characters allowed in a line,compute the minimum penalty to print the text.

输入格式

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 int 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.

样例

Input
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
Output
33
146

8 人解决,20 人已尝试。

9 份提交通过,共有 35 份提交。

7.5 EMB 奖励。

创建: 14 年,3 月前.

修改: 4 年,3 月前.

最后提交: 6 月,2 周前.

来源: kaohsiung 2006

题目标签