Minimizing Variance in Text Layout

Given \(N\) words, partition them into \(K\) lines while preserving the original order. The number of letters on a line is the sum of the letters of the words on that line (note that spaces between words are not considered).

The goal is to partition the words into exactly \(K\) segments such that the variance of the letters per line is minimized. The variance is defined as \[ \frac{1}{K} \sum_{i=1}^{K}\Bigl(S_i - \frac{S}{K}\Bigr)^2, \] where \(S_i\) is the number of letters in the \(i\)th line and \(S\) is the total number of letters over all words.

Since \(S\) is constant, minimizing the variance is equivalent to minimizing \(\sum_{i=1}^{K} S_i^2\). Your task is to compute the minimum possible variance and output it as a floating-point number with at least 6 digits after the decimal point.

inputFormat

The first line contains two integers \(N\) and \(K\) (with \(1 \leq K \leq N\)).

The second line contains \(N\) words separated by spaces. Each word consists only of letters.

outputFormat

Output the minimum variance value as a floating-point number, formatted with at least 6 decimal places.

sample

5 3
hello i am coding contest

0.666667