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 and Output

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.

The output is a single integer indicating the amount of time that will pass before all tasks can complete.

Sample Input

A 5
B 3 A
D 2 A
C 2 B
F 2 CE
E 4 DC

Sample Output

16