编程介的小学生
2017-02-23 08:46
采纳率: 92.7%
浏览 828
已采纳

Curriculum Made Easy

WishingBone has many courses at school. Usually he has to make out his own schedule. Some of the courses are easies than the others, and more often than not, mastery of a pre-requisite course helps the study of a subsequent course. For instance, Numerical Analysis takes Linear Algebra as a pre-requisite course so that it takes 50 hours to master NA with LA knowledge, which would otherwise take 100 hours. WishingBone learns at an average rate of 5 hours everyday, and is free to study his courses in any sequential order. Mathematically speaking, when WishingBone learns courses in the order c1, c2, c3, ..., cn, the time for course ci is the minimal time for learning ci without any pre-requisite or with pre-requisite cj where j < i. Notice that mastery of two pre-requisites does not make double effects. He wants to know what the minimal time he can finish a bunch of courses could be.

Input

The first line of input is a positive integer N <= 10, which is the number of test cases.

The first line of each case contains an integers n (0 < n <= 100), which is the total number of courses he has at school.

Descriptions of the n courses follow. First line of each description is in the form name time p, which are the name of the course (up to 30 upper and lower characters and the '_' character, with no other characters embedded), the time to learn this course without any pre-requisites, and the number of lines below.

Each p lines below are in the form name time which lists a possible pre-requisite and the substitute time.

After the descriptions is a line with a single integer m (0 <= m <= n), which is the number of courses WishingBone has already mastered. The next line lists the m names of the courses.

Output

For each test case output the minimal number of days WishingBone can finish the rest of his courses.

Sample Input

2
3
Economics 50 0
Linear_Algebra 50 0
Numerical_Analysis 100 2
Economics 1000
Linear_Algebra 50
2
Economics Linear_Algebra
3
Data_Structure 100 0
Algorithm_Design 80 1
Data_Structure 72
ACMICPC 60 2
Data_Structure 53
Algorithm_Design 47
0

Sample Output

10
44

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

2条回答 默认 最新

相关推荐 更多相似问题