고속도로와 자치주

먼 어느 나라에 도시가 $N$개 있다. 방금 선거가 끝나 새 총리가 뽑혔다. 이 나라에는 아직 도로가 하나도 없어서, 총리는 몇몇 도시를 양방향 고속도로로 잇고 자치주를 만들어 나라를 정비하기로 했다. 새로 놓은 도로를 따라 한 도시에서 다른 도시로 갈 수 있으면 두 도시는 같은 자치주에 속한다. 각 도시는 정확히 하나의 자치주에 속하고, 각 자치주는 도시를 하나 이상 포함한다.

도시는 2차원 좌표평면 위의 점이다. 두 도시를 잇는 도로는 두 점을 잇는 선분이고, 도로의 길이는 그 선분의 길이와 같다. 길이의 단위는 킬로미터다.

나라가 불황이라 예산이 부족하므로, 총리는 길이가 $D$킬로미터를 넘는 도로는 놓지 않기로 했다. 한편 총리는 작은 일에도 기뻐하는 사람이라, 어떤 자치주에 주민 수의 합이 $K$의 배수인 공집합이 아닌 도시 부분집합이 있으면 만족한다. 그 부분집합은 자치주의 모든 도시를 포함해도 된다. 예를 들어 $K = 4$이고 주민이 각각 3명, 5명, 7명인 도시로 이루어진 자치주가 있으면, 앞의 두 도시의 주민 수 합이 8이므로 총리는 만족한다.

총리가 만족하도록 도로를 놓을 수 있는 $D$의 최솟값을 구하라.

첫째 줄에 정수 $N$과 $K$가 주어진다 ($1 \le N \le 50000$, $1 \le K \le 30$).

다음 $N$개 줄에는 정수 $x_i$, $y_i$, $k_i$가 하나씩 주어진다 ($0 \le x_i, y_i, k_i \le 100000000$). 각각 도시의 $x$좌표, 도시의 $y$좌표, 그 도시의 주민 수다. 좌표가 같은 도시는 없다. 주민 수가 $K$로 나누어떨어지는 도시도 없다.

총리가 만족하도록 도로를 놓을 수 있는 $D$의 최솟값을 소수점 아래 셋째 자리까지 반올림해 한 줄에 출력한다. 답이 존재하는 입력만 주어진다.

첫 번째 예제에서는 모든 도시가 한 자치주에 모여야만 총리가 만족하고, 그렇게 만들 수 있는 $D$의 최솟값은 1.414다.

두 번째 예제에서는 앞의 다섯 도시가 한 자치주에 모이면 총리가 만족한다. $D = 5.657$이면 도시 1, 2, 3, 5를 도시 4와 이을 수 있고, 이때 도시 1부터 5까지의 주민 수 합이 11이라 11로 나누어떨어진다.