3390 Print Words in Lines

時間制限:1000ミリ秒
メモリ制限:65536KB

問題

Print Words in Lines
貴方は英語の文章を適切な文字数で区切って改行するソフトウェアを書かなくてはいけない。
このソフトウェアで定義される適切な改行とは、以下のとおりとします。

与えられる文章はアルファベットの文章が空白区切りで与えられ、文章に改行は存在しません。
この文章を改行で区切ります。
良い区切り方が出来るように以下の評価法が与えれます。

一行の文字数をｍとします。
まず各行に配置できる文字数は空白文字を入れてｍを超えてはいけません。

次に改行を入れおわった後の各行について調べ、(ｍ-その行の文字数)^2がその行のペナルティとなります。
これを全ての行について計算し合計したものが合計ペナルティとなります。
貴方はペナルティを最小にする改行の入れ方を探さなくてはいけません。

分かりにくいと思うので例で説明します。
一行の制限が20文字だったとします。

This is a text of fourteen words and the longest word has ten characters
という文章に以下のように改行を入れたとします。

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

このような区切り方をした場合、空白文字も入れて一行目は7文字。
一行目のペナルティは、制限20文字なので、(20-7)^2=169となり169が一行目のペナルティ。
他の行についても同様の計算がおこなわれます。

この時各行の2単語目からはスペースが入り、スペースも文字数として数えます。
改行は文字数として数えません。
この条件でペナルティが計算されます。

上記テキストは適切な改行を入れると合計ペナルティ33になるように改行を入れることが可能で、これが最も低いペナルティなので合計ペナルティ33が答えとなります。

一行頭の文字数の制限、単語の数、文章中の各単語の文字数が入力として与えられるのでその文章での最小ペナルティを算出して下さい。

一行目にデータセットの数Cが与えられます

一つのデータセットについての解説。
各データセットの一行目に一行に配置できる文字数制限ｍ、2行目は文章中の単語の数ｔ。
3行目以降は文章中の各単語の文字数がｔ行にわたって与えられます。

出力は、ペナルティの総計が最小となるよう改行で区切った時の最小ペナルティを一行に出力して下さい。

単語の数の上限ｔは一万単語、一行の文字数制限ｍは100文字までとなります。

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