Project Scheduling

PERT is a project management technique that splits a large project into tasks, fixes how long each task takes, and records which tasks must finish before another task may start. The result is drawn as a chart.

The picture above is the chart for the first sample input. Tasks A, B, C, D, E, and F take 5, 3, 2, 2, 4, and 2 days. Task E starts only after both C and D are finished, and once A is finished, B and D can run at the same time. Any number of tasks that do not wait for each other run at the same time.

Given a chart, write a program that computes the minimum time needed to finish the project.

The input has 1 to 26 lines, and each line describes one task. No task name appears twice. Each line contains the following items in order.

1. One uppercase letter, the name of the task
2. A natural number at most 1,000, the number of days the task takes
3. 0 to 25 uppercase letters written together with no spaces, the names of the tasks that must finish before this task starts

When the third item is absent, the line ends after two items. Every task named in the third item also appears in the input, and the input always allows all tasks to be completed.

Print the minimum time needed to finish all tasks on the first line.