TestVita

TCS is working on a new project called "TestVita". There are N modules in the project. Each module (i) has completion time denoted in number of hours (H_i) and may depend on other modules. If Module x depends on Module y then one needs to complete y before x.

As Project manager, you are asked to deliver the project as early as possible.
Provide an estimation of amount of time required to complete the project.

Input Format:

First line contains T, number of test cases.

For each test case: 

1.               First line contains N, number of modules.

2.               Next N lines, each contain:

o        (i) Module ID

o        (H_i) Number of hours it takes to complete the module

o        (D) Set of module ids that i depends on - integers delimited by space.

 

Output Format:

Output the minimum number of hours required to deliver the project.

Constraints:

1. 1 <= T <= 10

2. 0 < N < 1000; number of modules

3. 0 < i <= N; module ID 

4. 0 < H_i < 60; number of hours it takes to complete the module i

5. 0 <= |D| < N; number of dependencies

6. 0 < D_k <= N; module ID of dependencies

Sample Input and Output

SNo.	Input	Output
1	1 5 1 5 2 6 1 3 3 2 4 2 3 5 1 3	16

Explanation:

Module 2 depends on module 1, hence complete module 1 first

After completing module 1 we can complete module 2 and then module 3

Module 4 and 5 can be started simultaneously in parallel after module 3 is completed.

Hence the answer = 5 + 6 + 3 + 2 = 16

Note:

Please do not use package and namespace in your code. For object oriented languages your code should be written in one class.

Note:

Participants submitting solutions in C language should not use functions from / as these files do not exist in gcc

Note:

For C and C++, return type of main() function should be int.