Project Scheduling

A project management technique called Pert involves breaking a large project into a number of tasks, estimating the time required to perform each task, and determining which tasks can not be started until others have been completed. The project is then summarized in chart form. For example, the chart (which corresponds to the sample input below) indicates that tasks A, B, C, D, E and F each take 5, 3, 2, 2, 4, and 2 days respectively, that task E cannot complete until C and D are both completed, but that D can be performed in parallel with B and C. Write a program that accepts a Pert chart and computes the amount of time required to complete a project. Input The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs. Input will be from 1 to 27 lines, each corresponding to a different task. Each line will contain:

1. A single upper case letter serving as the name of a task. On the final line of input, this will be blank and the rest of that line is ignored.
2. An integer indicating the number of days required to complete that task.
3. 0-26 additional uppercase letters, each indicating another task that must complete before this one can begin. Output For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line. The output is a single integer indicating the amount of time that will pass before all tasks can complete.

2/2 Sample Input 2 A5 B3A D2A C2B F 2 CE E 4 DC A5 B3A D2A C2B F 2 CE E 4 DC Sample Output 16 16