452 - Project Scheduling

For the actual description of the input and output files, read the HTML version of the problem. Thanks.
NOTE: Multiple input but there is NO two blank lines in a row. This is an example of input/output for this problem:

INPUT:

2

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

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

OUTPUT:

16

16