코포고니아

코포고니아는 $n$개의 도시로 이루어진 나라이며, 현재 도로가 $n$개 있습니다. 이 도로들은 볼록 다각형을 이루며, 나라 이름도 여기서 왔습니다. 서로 다른 두 도시 사이에는 항상 정확히 두 가지 경로(시계 방향과 반시계 방향)가 있습니다. 그러나 일부 도시 쌍은 두 경로 중 짧은 쪽을 택해도 너무 오래 걸립니다.

설문 조사 결과, 어느 두 도시 사이의 경로 길이도 $m$ 이하일 때 시민들이 만족한다는 것이 밝혀졌습니다.

정부는 새 도로를 최대 $k$개까지 건설할 수 있습니다. 새 도로는 아직 직접 연결되지 않은 두 도시를 잇고, 길이는 두 도시 사이의 직선 거리와 같아야 합니다. 도로마다 건설 비용이 듭니다. 시민을 만족시키면서 총 건설 비용이 가장 적은 도로 집합을 구하십시오.

첫 줄에 정수 $n$, $k$, $m$이 주어집니다($4 \le n \le 50$, $1 \le k \le 10$, $m$은 이동 거리의 상한). 이어지는 $n$개의 줄에는 도시 $i$의 좌표 $x_i$, $y_i$가 주어집니다($0 \le x_i, y_i \le 10^4$). 도시 $i$와 $i+1$($1 \le i \le n-1$) 사이, 그리고 도시 $n$과 $1$ 사이에 도로가 있습니다. 도로는 양방향으로 통행할 수 있습니다.

이어지는 $k$개의 줄에는 정수 $u$, $v$, $c$가 주어집니다($1 \le u, v \le n$, $u \ne v$, $1 \le c \le 10^8$). 도시 $u$와 $v$ 사이에 비용 $c$로 도로를 건설할 수 있습니다. 도시의 위치는 모두 다릅니다. 후보 도로는 같은 도시 쌍을 두 번 나타내지 않으며, 이미 있는 도로와 같은 쌍도 포함하지 않습니다.

최소 한 개의 도로는 반드시 건설해야 합니다. 후보 도로를 모두 건설하면 모든 경로 길이가 $m$ 이하가 됩니다. $m$에 0.001을 더하거나 빼도 답은 바뀌지 않습니다.

시민을 만족시키는 도로 집합의 최소 비용을 출력하십시오.