Лекції#416
Є викладачів. Для кожного викладача відомо, коли починається і закінчується його лекція, а також мінімальна кількість студентів, яка повинна бути присутня на його лекції (якщо студентів менше, викладач не проведе лекцію). Усі викладачі викладають у різних будівлях, і для кожної пари будівель відомо, скільки часу потрібно, щоб перейти з однієї до іншої. Визначте мінімальну кількість студентів, необхідну для того, щоб усі викладачі змогли провести свої лекції. Один студент може відвідати кілька лекцій (якщо у нього вистачає часу фізично потрапити з однієї лекції на іншу). Не дозволяється спізнюватися на лекцію чи залишати її раніше завершення.
У першому рядку задано ціле число (1 \leq N \leq 20).
У другому рядку — додатних цілих чисел, не більших за — мінімальна кількість студентів, необхідна для кожної лекції відповідного викладача.
Далі йдуть рядків, у кожному з яких записано час початку та завершення лекції для кожного викладача, розділені пробілом. Час задано у форматі :, де — це години, а — хвилини. Гарантується, що всі лекції проходять в один день і тривають щонайменше одну хвилину.
Далі йде рядків, у кожному з яких по чисел. -те число в -му рядку — це час у хвилинах, потрібний для переходу з будівлі до будівлі (не більше доби). Перехід з однієї будівлі до іншої — прямий, без проходження через інші будівлі.
Викладачі пронумеровані від до . Номер будівлі відповідає номеру викладача, який у ній викладає.
Виведіть мінімальну кількість студентів, необхідну для того, щоб усі викладачі змогли провести свої лекції.
Приклад 1