Description

Given $n$ positive integers $a_1,a_2 ... a_n$. We want to partition them into $m$ groups so that the sums of the groups are as balanced as possible, i.e., the standard deviation of the group sums is minimized. The formula for the standard deviation is as follows:

$$\sigma = \sqrt{\frac 1m \sum\limits_{i=1}^m(\overline x - x_i)^2},\overline x = \frac 1m \sum\limits_{i=1}^m x_i$$

Here, $\sigma$ is the standard deviation, $\bar{x}$ is the average of the group sums, and $x_i$ is the sum of the $i$-th group.

Input Format

The first line contains two integers, representing the values of $n,m$ ($n$ is the number of integers, and $m$ is the number of groups).

The second line contains $n$ integers, representing $a_1,a_2 ... a_n$. Each integer is in the range $[1,50]$.

Integers on the same line are separated by spaces.

Output Format

Output one real number on a single line, representing the minimal value of the standard deviation, rounded to two decimal places.

6 3
1 2 3 4 5 6

0.00

Hint

Sample explanation: group as $(1,6)$, $(2,5)$, $(3,4)$.

Constraints

For $40\%$ of the testdata, it is guaranteed that $m \le n \le 10$, $2 \le m \le 6$.

For $100\%$ of the testdata, it is guaranteed that $m \le n \le 20$, $2 \le m \le 6$.

Translated by ChatGPT 5