405068: GYM101775 B Scapegoat

Aori is very careless so she is always making troubles. One day she does it again, with N big troubles! But this time she seems to be at ease because she has found M Inklings to take all the blames. Each trouble can be measured by a severity number a_i. Each trouble needs at least one Inkling to take the blame, and each Inkling can help Aori to take the blame for exactly one trouble. If two or more Inklings take the same trouble, they will take this blame together and discuss how to divide this trouble into.. some trivial things.. to reduce the pressure on each Inkling, as long as the total severity on Inklings is equal to the severity of this trouble.

Inklings are so warm so that Aori wants to think a way to let the variance of severity on each Inkling to be minimal. Could you help Aori make her scapegoats?

Formally, the variance of variables is the expectation of the squared deviation of a variable from its mean:

The first line of the input gives the number of test cases, T. T test cases follow.

For each test case, the first line contains two integers N and M, where N is the number of troubles, and M is the number of Inklings. The next line contains N integers a₁, a₂, ..., a_N representing the severity of the troubles that Aori makes.

• 1 ≤ T ≤ 100.
• 1 ≤ N ≤ M ≤ 2 × 10⁵.
• 1 ≤ a_i ≤ 10000.
• .

For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the minimal variance.

y will be considered correct if it is within an absolute or relative error of 10^- 8 of the correct answer.

3
3 6
1 2 3
5 10
5 6 7 8 9
6 6
1 1 4 5 1 4

Case #1: 0.000000000000
Case #2: 0.400000000000
Case #3: 2.888888888889

For the first sample, Aori can let one Inkling to take the first trouble's blame, two Inklings for the second, and three Inklings for the third. The severity on each Inkling is 1 unit, so their variance should be 0.