Параллельные процессы 2

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

Все независимые друг от друга процессы могут выполняться параллельно. Каждому процессу нужно время на подготовку перед запуском. Каждый процесс может начать выполнение не раньше, чем через D мс после возможного его запуска. Одновременно в системе может выполняться только K процессов. Если операционная система может запустить новый процесс, она выбирает процесс с наименьшим ID из всех процессов, готовых к запуску. Также в системе имеются M процессов, которые используют один и тот же ограниченный ресурс, поэтому не могут выполняться одновременно.

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

Входные данные

Входной файл INPUT.TXT в первой строке содержит три натуральных числа N, K, M (1 ≤ N, K ≤ 1000; 0 ≤ M ≤ 100). Далее идёт N строк, в каждой из которых записана информация об одном процессе, которая задается последовательностью целых чисел, разделенных пробелом: ID процесса B, время T выполнения процесса в миллисекундах, время D подготовки перед запуском в миллисекундах, далее следуют ID процессов A, которые должны быть выполнены до начала выполнения процесса B. Если процессы типа A отсутствуют, то четвертое число в строке равно 0. В последней строке через пробел указано M процессов (ID), которые не могут выполняться одновременно. Гарантируется, что все ID процессов различны и выполнение всех процессов возможно. (1 ≤ ID ≤ 10⁹; 1 ≤ T ≤ 10⁶; 0 ≤ D ≤ 1000).

Выходные данные

В выходной файл OUTPUT.TXT выведите ответ на задачу.

Пример

Автор задачи

Владимир Игоревич Лукьянчиков

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]