S. 14. The construction of a certain machine in a factory is divided into several phases. The number of minutes needed to complete a phase is known, together with the information which phases are required to precede that phase. Phases that are independent of one another can be performed simultaneously.
Make a schedule how to construct the machine so that the construction time is minimized, in a form that the starting minute for each phase is given.
The input consists of some positive integers encoding the phases. The first line contains the number of phases. Each subsequent line contains the name of a phase (also a number), its length (a positive integer), then the number of those phases on which the actual phase depends, finally their names separated by a space.
The first line of the output should contain the total construction time, then in each line the name of a phase together with its starting time, separated by a space.
See the example.
The source code of the program (s14.pas, s14.cpp, ...) should be submitted.
Deadline expired on 15 February 2006.