Minimum Completion Time for Teams' Tasks

In this problem, each team is assigned a number of tasks with precedence constraints. Each task has a unique task ID, a required time to complete, and a list of prerequisite tasks which must be completed before the task can start. For each team, you are given an integer m indicating the number of tasks and then m lines describing each task. Each task description consists of the task id, the time required for the task, the number of prerequisites, followed by the prerequisite task ids. Your goal is to compute the minimum total time needed for each team to complete all its tasks, under the assumption that a task can only begin after all its prerequisites are finished. Mathematically, if the tasks form a directed acyclic graph (DAG) with an edge from task ( u ) to task ( v ) representing that ( u ) is a prerequisite of ( v ), then the minimum completion time for the team is: [ T = \max_{v}{ (\text{time}(v) + \max_{u \in \text{pred}(v)}(T(u)) ) } ] where (T(u)=0) for tasks with no prerequisites. Assume that each team works independently.

This problem tests your ability to perform topological sorting and find the longest path in a DAG under the assumption that tasks can be executed as soon as their prerequisites are met.

inputFormat

The input is given via standard input (stdin). The first line contains two integers (n) and (k), where (n) is the number of teams and (k) (an unused parameter) is provided for legacy reasons. For each team, the input is structured as follows:

• A line with an integer (m) representing the number of tasks for the team.
• Then (m) lines follow, each describing a task. Each task line contains at least three integers: the task id, the time required to complete the task, and the number of prerequisite tasks. If the number of prerequisites is greater than zero, it is followed by that many integers, each representing a prerequisite task id.

The tasks for different teams are given consecutively.

outputFormat

For each team, output a single line containing a single integer – the minimum total time required for the team to complete all tasks. The answers for the teams should be printed in the same order as the teams appear in the input, each on a new line.## sample

2 0
3
1 3 0
2 2 1 1
3 4 2 1 2
4
1 2 0
2 1 0
3 3 1 1
4 5 1 3

9
10