경비원

경비 회사가 여러 직선 복도를 따라 놓인 귀중품을 지키기 위해 경비원을 배치한다. 각 복도는 폭이 $0$인 선분으로 모형화한다. 귀중품은 이름표가 붙은 점에 놓이며, 각 점은 음이 아닌 정수 가치를 가진다(가치가 $0$이면 그 점에는 귀중품이 없다).

경비원은 복도 위의 임의의 지점에 설 수 있으며, 여러 복도가 만나는 교차점에도 설 수 있다. 경비원은 자신이 서 있는 위치를 지나는 복도 위에 있는 모든 귀중품을 볼 수 있고, 따라서 지킬 수 있다. 경비원은 모퉁이 너머를 볼 수는 없다. 어떤 귀중품이 경비원의 위치를 지나지 않는 다른 복도 위에 있다면, 직선 거리로 아무리 가깝더라도 그 경비원은 그 귀중품을 지키지 못한다.

귀중품에 대한 위험도는 그 가치에, 그 귀중품을 볼 수 있는 가장 가까운 경비원까지의 거리를 곱한 값이다.

$$\text{위험도} = \text{가치} \times \min_{\text{그 귀중품을 볼 수 있는 경비원}} \text{거리}(\text{경비원}, \text{귀중품})$$

배치도와 경비원 수 $g$가 주어질 때, 모든 귀중품에 대한 위험도의 최댓값이 가능한 한 작아지도록 $g$명의 경비원을 배치하라. 그 최소화된 최대 위험도를 구하라. 만약 모든 귀중품이 적어도 한 명의 경비원에게 보이도록 $g$명을 배치할 수 없다면, 경비원이 부족하다고 답하라.

입력은 $1$개부터 $16$개까지의 데이터 집합으로 이루어지며, 마지막에 $0$ 하나만 있는 줄이 온다.

각 데이터 집합의 첫 줄에는 정수 세 개 $p$ $c$ $g$가 있다. 각각 이름표가 붙은 점의 수, 복도의 수, 배치할 경비원의 수이며 $1 < p < 12$, $0 < c < 12$, $0 < g < 5$이다.

이어서 네 개의 토큰으로 이루어진 묶음이 $p$개 온다. 각 묶음 $L$ $x$ $y$ $v$는 좌표 $(x, y)$에 있고 이름표가 $L$이며 가치가 $v$인 귀중품을 나타낸다. 이름표는 $A$부터 시작하는 연속된 대문자이다. 모든 수는 $1000$ 미만이다. 모든 점은 서로 다르다. $v = 0$이면 그 점에 귀중품이 없다는 뜻이다. 귀중품이 있는 점의 수는 $g$ 이상이다.

마지막으로 복도마다 하나씩 토큰 $c$개가 온다. 각 토큰은 이름표들의 문자열로, 복도의 한 끝에서 다른 끝까지 차례대로 그 복도 위의 모든 점을 나열한다. 여기에는 양 끝점, 다른 복도와의 모든 교차점, 그 복도 위의 모든 귀중품이 포함된다. 데이터 집합의 모든 점은 적어도 하나의 복도 위에 있다.

데이터 집합마다 한 줄을 출력한다. 모든 귀중품이 어떤 경비원에게 보이도록 $g$명의 경비원을 배치할 수 없으면 too few guards를 출력한다. 그렇지 않으면 최소화된 최대 위험도 $r$, 즉 $g$명의 경비원을 놓는 모든 배치에 대해 어떤 한 귀중품이 받는 위험도의 최댓값 중 가능한 가장 작은 값을 소수점 아래 정확히 두 자리로 반올림하여 출력한다.