Problemas
지금 당신은 한 문단의 텍스트를 출력해야 한다.
텍스트란 영문자와 빈칸으로 구성되어있다.
텍스트를 출력하고자 할 때, 우리는 한 단어(공백없이 이어진 단어)를 한번씩,
텍스트에서 나오는 순서대로 출력을 하려고 한다.
단어들은 한줄 내에 출력되어야 하고, 한 줄은 최대 M개의 글자를 출력할 수 있다.
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
그러나, 출력을 할 때 한 줄의 맨 뒤에 너무 많은 빈칸을 두게 되면 출력시에 페널티를 받게 된다.
페널티는 M글자와 실제 출력된 글자의 차이의 제곱을 한 값이다.
예를 들어 첫 번째 칸의 경우 7개의 글자를 출력하였으므로, (20-7)*(20-7) = 169의 페널티를 받게 된다.
단어 사이에 들어가는 공백은 글자로 치기 때문에 페널티로 간주하지 않는다.
전체 페널티는 모든 줄의 페널티를 합한 값이다.
허용되는 줄의 크기와 단어들의 길이가 주어졌을 때, 페널티를 최소화 하는 프로그램을 작성하라.
Entrada
첫 번째 줄에는 테스트케이스의 개수 C가 입력된다.
그 다음 줄부터 C개의 테스트 케이스가 입력되는데,
테스트 케이스의 첫 번째 줄은 문자를 찍을 때의 한 줄에서 허용하는 최대 글자 수 M이다.
그 다음 단어의 개수 N이 입력된다. 그리고 그 다음 줄부터 N개의 단어의 길이가 입력된다.
모든 단어의 길이는 M이하이다. N은 최대 10,000이며, M은 최대 100이다.
Salida
각 테스트 케이스에 대한 최소의 페널티를 한 줄에 하나씩 출력한다.
Ejemplo
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
Debes iniciar sesión para escribir código.