There are \textbf{N} speakers. For each of them know how much begins and ends with his lecture. We also know the minimum number of students who must attend his lectures (if fewer students, the lecturer will not lecture). All the lecturers teach in different buildings, and for each pair of buildings known to the transition from one to another. Need to know what the minimum number of students is essential that all lecturers have conducted their lectures. A student can go to a few lectures (if he has time to physically). At the lecture can not be late and can not leave before its completion. \textbf{Input} The first line of the input file contains an integer \textbf{N} (\textbf{1} <= \textbf{N} <= \textbf{20}). The second line contains \textbf{N} positive integers not exceeding \textbf{50} - the minimum number of students who Dolny attend the lectures of the teacher. Then there are \textbf{N} rows in which a gap defined start and end of lectures of the teachers. Time is given in the format \textbf{hh}:\textbf{mm}, where \textbf{hh} - hours, \textbf{mm} - minutes. It is guaranteed that all lectures are held in one day and lasts at least one minute. Then there are \textbf{N} rows of \textbf{N} numbers each. \textbf{j}-th number in the \textbf{i}-th row specifies the transition from the \textbf{i}-th body in the \textbf{j}-th number of minutes (at most days). Move from one body to another should be directly, without going into other corps. Lecturers are numbered from \textbf{1} to \textbf{N}. Number hull coincides with the lecturer, who conducts classes in this package. \textbf{Output} In the first line of the output file print out the minimum number of students required to ensure that all lecturers have conducted their studies.