n개의 옷과 세탁기가 있다. 세탁기는 충분히 크기가 커서 모든 세탁물을 한 번에 세탁하는 것이 가능하다.

그러나, 이염(의류에서 염료가 빠져 그 의류의 다른 부분이나 다른 의류로 염료가 옮겨 배는 현상)되는 것을 조심해야한다.

만약 서로 다른 색상의 옷을 세탁기에 넣고 세탁하면 한 옷의 염료가 다른 옷을 얼룩지게 할 수 있다.

정확하게는 r_i, g_i, b_i는 i번째 옷의 빨간색, 녹색, 파란색의 양을 나타내는데, n개의 옷을 함께 세탁할 때 이염되는 정도인 c는 다음과 같이 정의된다:

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

이때, r, g, b는 각각 r_i, g_i, b_i의 평균을 의미한다. i번째 옷은 3차원 RGB 공간의 점 (r_i, g_i, b_i)로 정의되고, RGB 공간에서 세 점(옷)이 같은 선에 없고, 네 점(옷)이 같은 평면에 없다고 가정할 수 있다.

세탁기는 전기를 많이 소모하기 때문에 n개의 옷을 최대 k개의 그룹으로 나누어 각 그룹별로 세탁기를 돌려야 하는데, 총 이염도는 각 그룹 세탁의 c의 합계이다.

n개의 옷과 k개의 색상 정보가 주어지면, 최소 총 이염도를 계산하는 프로그램을 작성하시오.

세탁기(Washer) timer 1s memory 512MB

세탁기(Washer) 1s 512MB