Lectures#416
There are lecturers. For each lecturer, you know when their lecture starts and ends, as well as the minimum number of students who must attend their lecture (if there are fewer students, the lecturer will not give the lecture). All lecturers teach in different buildings, and for each pair of buildings, the time required to move from one to another is known. Determine the minimum number of students required so that all lecturers are able to conduct their lectures. A student can attend multiple lectures (if they have enough time to physically get from one to another). It is not allowed to be late to a lecture or to leave before it ends.
The first line contains an integer (1 \leq N \leq 20).
The second line contains positive integers not exceeding — the minimum number of students required to attend each lecturer's lecture.
Then follow lines, each containing the start and end time of each lecturer's lecture, separated by a space. The time is given in the format :, where is the hour and is the minute. It is guaranteed that all lectures are held in one day and last at least one minute.
Next, there are lines each containing numbers. The -th number in the -th line is the time in minutes to move from building to building (no more than a day). Moving from one building to another is direct, without passing through other buildings.
Lecturers are numbered from to . The number of the building corresponds to the number of the lecturer who teaches in it.
Print the minimum number of students required to ensure that all lecturers can conduct their lectures.
Example 1