题目描述

我们有一段需要打印的文本段落。文本由一系列单词组成，每个单词由若干字符构成。打印文本时，我们需要按照单词在文本中出现的顺序逐个打印。单词将被打印在多行中，且每行最多打印 $M$ 个字符。如果一行中有足够的空间，可以打印多个单词。然而，当一行打印多个单词时，相邻单词之间必须恰好用一个空格字符隔开。例如，给定以下文本：

This is a text of fourteen words and the longest word has ten characters

我们可以将这段文本打印为每行不超过 $20$ 个字符的形式，如下所示：

This is  
a text of  
fourteen words  
and the longest  
word  
has ten characters  

然而，如果某行实际打印的字符数少于 $20$，则需要支付一定的惩罚值。惩罚值等于 $(20 - \text{实际字符数})^2$。例如，第一行实际打印了 $7$ 个字符，因此惩罚值为 $(20 - 7)^2 = 169$。总惩罚值为所有行的惩罚值之和。给定文本和每行允许的最大字符数 $M$，计算打印文本的最小总惩罚值。

输入格式

• 第一行是测试用例的数量 $C$。
• 每个测试用例的第一行是每行允许的最大字符数 $M$。
• 每个测试用例的第二行是文本中的单词数量 $N$。
• 接下来的 $N$ 行是文本中每个单词的字符长度。
  保证：
  • 每个单词的长度不超过 $M$，
  • $N$ 最多为 $10000$，
  • $M$ 最多为 $100$。

输出格式

输出 $C$ 行，每行对应一个测试用例的最小惩罚值。

样例输入

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  

样例输出

33  
146  

来源

Kaohsiung 2006