Project Scheduling

Interview

Time limit2sMemory limit512 MB

Summary

Given each task's duration and its prerequisite tasks, find the minimum total time to finish the whole project.

Level: Medium5 of 10
Topics: Topological sort, Dynamic programming, Graph, DFS
Solved: No attempts yet

Problem

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.

Input

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.

One uppercase letter, the name of the task
A natural number at most 1,000, the number of days the task takes
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.

Output

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

Examples5

Example 1
Input
```
A 5
B 3 A
D 2 A
C 2 B
F 2 CE
E 4 DC
```
Expected output
```
16
```
Example 2
Input
```
A 7
```
Expected output
```
7
```
Example 3
Input
```
A 1
B 1 A
C 1 B
D 1 C
E 1 D
```
Expected output
```
5
```
Example 4
Input
```
A 4
B 6 A
C 1 A
D 2 BC
```
Expected output
```
12
```
Example 5
Input
```
Z 2
M 5 Z
A 1 M
```
Expected output
```
8
```