Calender Colors

Taro는 프로그래밍 콘테스트 동아리 소속이다. 이 동아리 회원들은 Great Web Calender라는 시스템으로 일정을 관리한다.

Taro는 방금 친구 몇 명을 자신의 캘린더에 추가해서 그들의 일정을 자신의 캘린더에서 볼 수 있게 했다. 그런데 시스템이 모든 일정을 한 가지 색으로 표시하고 있어서 친구들의 일정이 전부 섞여 보인다. 각 일정이 누구의 것인지 구분하기 어려워 관리하기가 힘들다.

사실 이 캘린더 시스템에는 일정을 가진 사람에 따라 일정 항목의 색을 바꾸는 기능이 있다. Taro는 그 기능으로 일정을 색깔별로 구분하려고 한다.

Taro가 쓸 수 있는 색과 회원 수가 주어졌을 때, 모든 일정 항목에 색을 칠할 색의 부분집합을 계산하는 것이 과제다. 색은 "Lab 색 공간"으로 주어진다.

Lab 색 공간에서 두 색 사이의 거리는 각 성분 차이의 제곱합으로 정의된다. Taro는 집합 안의 모든 색 쌍에 대한 거리의 합을 최대로 만드는 색의 부분집합을 골라야 한다.

입력은 다음과 같은 형식이다.

N M
L0 a0 b0
L1 a1 b1
…
LN−1 aN−1 bN−1

첫 줄에는 두 정수 N과 M(0≤M≤N≤20)이 주어진다. N은 입력으로 주어지는 색의 수, M은 Taro가 색을 고를 친구의 수다. 이어지는 N개 줄에는 각각 Lab 색 공간의 색 하나를 나타내는 세 정수 L(0.0≤L≤100.0), a(−134.0≤a≤220.0), b(−140.0≤b≤122.0)가 주어진다.

총 거리의 최댓값을 출력한다. 출력의 오차는 10−5보다 크면 안 된다.