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