The Mark of a Wizard

Goblins have a web of tunnels leading up from their underground lairs. In the schematic of one of their simpler systems, the vertical direction on the page points upward. The lair is at label $A$ and the surface (the exit) is at label $F$; the other labels mark tunnel intersections. Tunnels heading toward the surface from an intersection are drawn going upward. This is a 2D schematic of a 3D system, so paths that appear to cross anywhere other than at a lettered intersection do not actually meet (for example, edge $BD$ does not intersect edge $CE$).

A group of good wizards often needs to rush up through such tunnels to the surface along a path that takes the minimum possible time. Many upward tunnels can leave an intersection, and in general there is no obvious way to pick the best one. The wizards mapped the systems, recording the time needed to travel up from one intersection to the next. In a hurry they cannot consult elaborate notes, and they do not want to help enemies who might be rushing through the same tunnels. So they place a very discreet private mark at some intersections. A mark on a tunnel leaving an intersection means a wizard should take that tunnel. Because the system might be discovered, especially if there are too many marks, they want to mark as few intersections as possible while still guaranteeing that a wizard who always heads up and always takes a marked tunnel where one is shown will emerge in the minimum time.

Take the first system described above. One valid set of marks points from $A$ to $B$ and from $B$ to $C$. There is only one way up from $C$, so a wizard following the marks goes $A \to B \to C \to F$ in total time $3 + 1 + 4 = 8$, the minimum possible.

The same system needs only one mark: a single mark at $E$ directing a wizard to $D$. This does not fully determine a path -- from $A$ a wizard may go toward $B$ or $E$, and from $B$ there are again two choices -- but every one of these upward paths covers the same minimum time $8$. The mark at $E$ cannot be removed, or a wizard might take $A \to E \to C \to F$ for time $2 + 3 + 4 = 9$. So one mark suffices for this system (another single-mark option is a mark at $A$ pointing to $B$).

Help the wizards plan their marks. Be careful with your algorithm -- this can be time-consuming.

The input consists of 1 to 16 data sets, followed by a line containing only $0$.

The first line of a data set contains an integer $n$ ($2 \le n \le 17$), the number of labeled places; these are the starting point, the ending point, and any intersections in between.

Each of the next $n$ lines describes the upward tunnels from one labeled point. Every line has the same form, with blank-separated parts: first a letter labeling the tunnel's starting point, then an integer $u$, the number of upward tunnels from that point. After the label and $u$ come $u$ pairs (letter, time), each giving the integer $time$ ($1 \le time \le 500$) to travel through a tunnel from the current point to the point with that letter. The labels at the start of the $n$ lines are taken in order from the beginning of the capital letters. $A$ is always the starting point and the last letter used is always the exit. Only the final line (the exit) has $u = 0$; every earlier line has $1 \le u \le 6$.

Limiting assumptions:

• Wizards may only follow upward tunnels out of any intersection.
• The total number of tunnels is at most 35.
• There is always a minimum-time path from the lair to the surface, and it uses at most 7 tunnels.
• Every labeled point other than the start and the exit has at least one tunnel coming up to it and at least one heading up from it.

The first data set of the example corresponds to the tunnel system described above.

Print one line for each data set with two space-separated numbers: the minimum time to travel from the lair to the surface, and the minimum number of marks needed to guarantee that every wizard travels in that minimum time.