|
Задача:
Имеется N лекторов. Для каждого из них известно во сколько начинается
и заканчивается его лекция. Также известно минимальное
число студентов, которые должны присутствовать на его лекции (если
студентов меньше, то лектор не будет читать лекцию). Все
лекторы ведут занятия в разных корпусах и для каждой пары корпусов
известно время перехода из одного в другой. Требуется узнать, какое
минимальное число студентов необходимо, чтобы все лекторы провели свои
лекции. Один студент может ходить на несколько лекций (если он физически
успевает). На лекцию нельзя опаздывать и нельзя уходить раньше ее
окончания.
Формат входного файла:
Первая строка входного файла содержит целое число N (1 <= N <= 20).
Вторая строка содержит N целых положительных чисел, не превосходящих 50 - минимальное количество студентов,
которые долны присутствовать на лекции соответствующего преподавателя.
Затем идут N строк, в которых через пробел заданы время начала и окончания лекций соответствующих преподавателей.
Время задано в формате hh:mm, где hh - часы, mm - минуты. Гарантируется, что все лекции проходят в один день и
длятся минимум одну минуту. Затем идут N строк по N чисел в каждой. j-ое число в i-ой строке задает время перехода
из i-ого корпуса в j-ый в минутах (не превосходит суток). Переходить из одного корпуса в другой нужно напрямую, не заходя в другие корпуса.
Лекторы нумеруются числами от 1 до N. Номер корпуса совпадает с номером лектора, который проводит занятие в данном корпусе.
Формат выходного файла:
В первой строке выходного файла выведите минимальное количество студентов, необходимых
для того, чтобы все лекторы провели свои занятия.
Примеры:
| STDIN | STDOUT |
3
1 1 3
10:00 11:00
10:15 10:55
11:10 12:00
0 5 10
5 0 5
10 5 0
|
3
|
| STDIN | STDOUT |
3
1 1 3
10:00 11:00
10:15 10:55
11:09 12:00
0 5 10
5 0 5
10 5 0
|
4
|
|
