TCS is working on a new project called “TestVita”. There areNmodules in the project. Each module(i)has completion time denoted in number of hours(Hi)and may depend on other modules. If Modulexdepends on Moduleythen one needs to completeybeforex.
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.
First line contains
T, number of test cases.
For each test case:
1.First line containsN, number of modules.
2.NextNlines, each contain:
o(Hi)Number of hours it takes to complete the module
o(D)Set of module ids thatidepends on – integers delimited by space.
Output the minimum number of hours required to deliver the project.
1. 1 <= T <= 10
2. 0 < N < 1000; number of modules
3. 0 < i <= N; module ID
4. 0 < Hi< 60; number of hours it takes to complete the module i
5. 0 <= |D| < N; number of dependencies
6. 0 < Dk<= N; module ID of dependencies
Sample Input and Output
1 5 1 5 2 6 1 3 3 2 4 2 3 5 1 3
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.