Лекции
Имеется N лекторов. Для каждого из них известно во сколько начинается и заканчивается его лекция. Также известно минимальное число студентов, которые должны присутствовать на его лекции (если студентов меньше, то лектор не будет читать лекцию). Все лекторы ведут занятия в разных корпусах и для каждой пары корпусов известно время перехода из одного в другой. Требуется узнать, какое минимальное число студентов необходимо, чтобы все лекторы провели свои лекции. Один студент может ходить на несколько лекций (если он физически успевает). На лекцию нельзя опаздывать и нельзя уходить раньше ее окончания.
Входные данные Первая строка входного файла содержит целое число N (1 <= N <= 20). Вторая строка содержит N целых положительных чисел, не превосходящих 50 - минимальное количество студентов, которые долны присутствовать на лекции соответствующего преподавателя. Затем идут N строк, в которых через пробел заданы время начала и окончания лекций соответствующих преподавателей. Время задано в формате hh:mm, где hh - часы, mm - минуты. Гарантируется, что все лекции проходят в один день и длятся минимум одну минуту. Затем идут N строк по N чисел в каждой. j-ое число в i-ой строке задает время перехода из i-ого корпуса в j-ый в минутах (не превосходит суток). Переходить из одного корпуса в другой нужно напрямую, не заходя в другие корпуса. Лекторы нумеруются числами от 1 до N. Номер корпуса совпадает с номером лектора, который проводит занятие в данном корпусе.
Выходные данные В первой строке выходного файла выведите минимальное количество студентов, необходимых для того, чтобы все лекторы провели свои занятия.