Guard

A security company posts guards to protect valuable items placed along a set of straight corridors. Each corridor is modeled as a line segment of zero width. Items sit at labeled points, and every point carries a non-negative integer value (a value of $0$ means there is no valuable item there).

A guard may stand at any point along a corridor, including at an intersection where several corridors cross. A guard can see, and therefore protect, every item that lies on a corridor passing through the guard's own position. A guard cannot see around a corner: if an item lies on a different corridor that does not pass through the guard's position, that guard does not protect it, no matter how close it is in a straight line.

The risk to a valuable item equals its value multiplied by the distance to the nearest guard that can see it.

$$\text{risk} = \text{value} \times \min_{\text{guards that see the item}} \text{dist}(\text{guard}, \text{item})$$

Given a site layout and a number of guards $g$, place the $g$ guards so that the maximum risk over all valuable items is as small as possible, and report that minimized maximum risk. If the $g$ guards cannot be positioned so that every valuable item is seen by at least one guard, report that there are too few guards.

The input contains from one to sixteen datasets, followed by a line containing a single $0$.

The first line of each dataset holds three integers $p$ $c$ $g$: the number of labeled points, the number of corridors, and the number of guards to place, with $1 < p < 12$, $0 < c < 12$, and $0 < g < 5$.

Next come $p$ groups of four tokens $L$ $x$ $y$ $v$: a point labeled $L$ at coordinates $(x, y)$ that holds an item of value $v$. Labels are consecutive capital letters starting at $A$. All numbers are less than $1000$. Every point is distinct. A value of $v = 0$ means there is no valuable item at that point. The number of points that hold a valuable item is at least $g$.

Finally, $c$ tokens follow, one per corridor. Each token is a string of point labels listing, in order from one end of the corridor to the other, every point on that corridor: both endpoints, every intersection with another corridor, and every valuable item on it. Every point of the dataset lies on at least one corridor.

Print one line per dataset. If the $g$ guards cannot be placed so that every valuable item is seen by some guard, print too few guards. Otherwise print the minimized maximum risk $r$ — the smallest possible value, over all placements of the $g$ guards, of the largest risk to any single valuable item — rounded to exactly two digits after the decimal point.