17978번 - Washer 다국어

You have n clothes and a washer. The washer is large enough to wash all clothes at once. However, we should worry about the color transfer: if we put clothes of different colors in the washer, the dye from one may stain another. Precisely, let r_i, g_i, b_i denote the amount of red, green, blue color of the i-th clothes. When n clothes are washed together, the color transfer c is defined by

\[c = \sum_{i=1}^{n}{(r_i - r)^2 + (g_i - g)^2 + (b_i - b)^2}\]

where r, g, and b are the averages of r_i, g_i, b_i, respectively. The i-th clothes with r_i, g_i, and b_i is defined as a point (r_i, g_i, b_i) in 3-dimensional RGB space. You can assume that no three points (clothes) are on a same line and no four points (clothes) are on a same plane in RGB space.

The washer consumes a lot of electricity, and you have to partition n clothes into at most k groups, and run the washer for each group. The total color transfer is the sum of color transfers from each run. Given the color information of n clothes and k, write a program to calculate the minimum total color transfer.

Your program is to read from standard input. The first line contains two integers n (1 ≤ n ≤ 100) and k (1 ≤ k ≤ 2). In the following n lines, the i-th line contains three integers r_i, g_i, b_i (0 ≤ r_i, g_i, b_i ≤ 1,000).

Your program is to write to standard output. Print exactly one line containing the minimum total color transfer, rounded to the sixth decimal point.