Description

He wrote $N$ words in total. For aesthetics, you must split the $N$ words into $K$ lines. The relative order of words cannot change. To simplify the problem, ignore spaces between words.

Xiao Hong likes neat letters. Xiao Ming wants to win her heart, so he asks you to write a program to typeset the words so that the variance of the number of letters per line is minimized. Please output the minimum variance.

Input Format

Line $1$: two positive integers $N, K$.

Line $2$: $N$ space-separated words.

Output Format

One line: a decimal number with exactly one digit after the decimal point representing the minimum variance of letters per line.

4 2
xxx xxxxx xxxx xx
（输入的本来是一封情书，被和谐了……）

1.0

Hint

Sample Explanation:

xxx xxxxx
xxxx xx

$1 \div 2 \times ((8-7)^2+(6-7)^2) = 1$.

Constraints:

For $30\%$ of the testdata, $N \leq 100$, $K \leq 3$.

For all testdata, $N \leq 1000$, $K \leq 100$, word length $\leq 20$.

Translated by ChatGPT 5