Є \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{Вихідні дані} У першому рядку вихідного файлу виведіть мінімальну кількість студентів, потрібних для того, щоб всі лектори провели свої заняття.