Вам предстоит участвовать в
написании новой операционной системы для многопроцессорных систем. В любой
момент времени операционная система может исполнять произвольное количество
независимых процессов, и время, за которое каждый процесс будет выполнен, не
зависит от того, сколько процессов выполнялось одновременно с ним.
Однако одновременно могут
выполняться только независимые процессы. В некоторых случаях процесс A
может использовать данные, полученные процессом B (и произвольным
количеством других процессов). Тогда к моменту старта процесса A все
процессы, от которых он зависит, уже должны отработать.
По времени исполнения
нескольких процессов и таблице зависимости между этими процессами нужно
вычислить время исполнения заданной группы процессов.
В первой строке входных
данных находится число N (2 <=
N <=
20) — количество процессов, которые нужно выполнить.
Во второй строке через
пробел записаны
N чисел от 1 до
1000; i-ое число — это время в миллисекундах, требуемое для исполнения i-го
процесса.
Далее идут N строк, описывающих зависимости между
процессами. В каждой из них находятся по N символов 'Y'
и 'N'
(заглавных латинских букв). Символ 'Y'
в i-ой из этих строк на j-ом месте означает,
что для запуска i-го процесса требуется завершить j-ый. Символ 'N' означает, что i-ый процесс не
зависит от j-го напрямую.
Выведите минимальное время
в миллисекундах, требуемое для выполнения всех процессов или –1, если при
заданной таблице зависимостей группу процессов нельзя выполнить.
|
Пример ввода 1
3
100
200 300
NNN
NNN
YYN
Пример вывода 1
500
|
Пример ввода 2
2
10
10
NY
YN
Пример вывода 2
-1
|
