В файле со­дер­жит­ся ин­фор­ма­ция о со­во­куп­но­сти N вы­чис­ли­тель­ных про­цес­сов, ко­то­рые могут вы­пол­нять­ся па­рал­лель­но или по­сле­до­ва­тель­но. Будем го­во­рить, что про­цесс B за­ви­сит от про­цес­са A, если для вы­пол­не­ния про­цес­са B не­об­хо­ди­мы ре­зуль­та­ты вы­пол­не­ния про­цес­са A. В этом слу­чае про­цес­сы могут вы­пол­нять­ся толь­ко по­сле­до­ва­тель­но.

Ин­фор­ма­ция о про­цес­сах пред­став­ле­на в файле в виде таб­ли­цы. В пер­вой стро­ке таб­ли­цы ука­зан иден­ти­фи­ка­тор про­цес­са (ID), во вто­рой стро­ке таб­ли­цы  — время его вы­пол­не­ния в мил­ли­се­кун­дах, в тре­тьей стро­ке пе­ре­чис­ле­ны с раз­де­ли­те­лем «;» ID про­цес­сов, от ко­то­рых за­ви­сит дан­ный про­цесс. Если про­цесс яв­ля­ет­ся не­за­ви­си­мым, то в таб­ли­це ука­за­но зна­че­ние 0.

Опре­де­ли­те ми­ни­маль­ное время, через ко­то­рое за­вер­шит­ся вы­пол­не­ние всей со­во­куп­но­сти про­цес­сов, при усло­вии, что все не­за­ви­си­мые друг от друга про­цес­сы могут вы­пол­нять­ся па­рал­лель­но.

Ти­по­вой при­мер ор­га­ни­за­ции дан­ных в файле:

В дан­ном слу­чае не­за­ви­си­мые про­цес­сы 1 и 2 могут вы­пол­нять­ся па­рал­лель­но, при этом про­цесс 1 за­вер­шит­ся через 4 мс, а про­цесс 2  — через 3 мс с мо­мен­та стар­та. Про­цесс 3 может на­чать­ся толь­ко после за­вер­ше­ния обоих про­цес­сов 1 и 2, то есть через 4 мс после стар­та. Он длит­ся 1 мс и за­кон­чит­ся через 4 + 1  =  5 мс после стар­та. Вы­пол­не­ние про­цес­са 4 может на­чать­ся толь­ко после за­вер­ше­ния про­цес­са 3, то есть через 5 мс. Он длит­ся 7 мс, так что ми­ни­маль­ное время за­вер­ше­ния всех про­цес­сов равно 5 + 7  =  12 мс.

Вы­пол­ни­те за­да­ния, ис­поль­зуя дан­ные из файла ниже: