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