eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Лекції

Лекції

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Є N лекторів. Для кожного з них відомо у скільки починається і закінчується його лекція. Також відоме мінімальне число студентів, які повинні бути присутні на його лекції (якщо студентів менше, то лектор не буде читати лекцію). Всі лектори проводять заняття в різних корпусах і для кожної пари корпусів відомо час переходу з одного в інший. Потрібно взнати, яка мінімальна кількість студентів потрібна, щоб всі лектори провели свої лекції. Один студент може ходити на декілька лекцій (якщо він фізично встигає). На лекцію не можна запізнюватись і не можна з неї йти раніше її закінчення.

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

Вихідні дані У першому рядку вихідного файлу виведіть мінімальну кількість студентів, потрібних для того, щоб всі лектори провели свої заняття.

Приклад

Вхідні дані #1
3
1 1 3
10:00 11:00
10:15 10:55
11:09 12:00
0 5 10
5 0 5
10 5 0
Вихідні дані #1
4