Majestic Gourmet University

Majestic Gourmet University awards the Majestic International Cooking Degree to a large number of students every year.

Every student takes two mandatory classes, French Cuisine (FC) and Italian Cuisine (IC). Two disjoint groups of teachers run them, the FC teachers and the IC teachers. Both classes run as weekly cooking labs and have a limited number of seats, $K_{FC}$ students per FC lab and $K_{IC}$ students per IC lab. Several lab instances of each class therefore run every week, and each instance has its own weekly timeslot and its own assigned teacher. One more complication exists. Some of the teachers are in open conflict with each other because they disagree on teaching methods.

Every year the heads of the FC department and the IC department propose a number of weekly lab instances, and Bob from the Planning Office picks a subset of these propositions so that every student gets a valid timetable, which means:

• Every student attends exactly one weekly FC lab and one weekly IC lab. A student cannot attend two labs whose timeslots overlap, and cannot attend two labs separated by less than 5 minutes, because switching classrooms takes time.
• The seat limits hold: at most $K_{FC}$ students in an FC lab, and at most $K_{IC}$ students in an IC lab.
• If FC teacher A is in conflict with IC teacher B, then no student of a lab taught by A attends a lab taught by B.
• Bob also wants as many free days as possible. Among all valid choices, the starting times of the picked labs must fall on the fewest possible days of the week. Those days do not have to be consecutive.

Timeslots are compared over the whole week. A lab that starts on day $d$ at $h$ hours $m$ minutes runs from minute $1440(d-1) + 60h + m$ to minute $1440(d-1) + 60h + m + 60L$, where $L$ is the duration of that class in hours. A student can attend two labs exactly when one of them starts at least 5 minutes after the other one ends.

Some teachers may take no lab instance at all, and one teacher may be in charge of several labs.

Help Bob and report the smallest possible number of days.

Every line holds integers separated by single spaces.

The first line holds $S$, the number of registered students.

The second line holds $N_{FC}$, $K_{FC}$, $D_{FC}$ and $T_{FC}$: the number of FC lab propositions, the seat limit of every FC lab, the duration in hours of every FC lab, and the number of FC teachers.

Each of the next $N_{FC}$ lines describes one proposed FC lab slot with four integers $d$, $h$, $m$ and $t$: the day of the week, the starting hour, the starting minute, and the FC teacher in charge.

The next line holds $N_{IC}$, $K_{IC}$, $D_{IC}$ and $T_{IC}$ with the same meanings for IC.

Each of the next $N_{IC}$ lines describes one proposed IC lab slot in the same format.

The next line holds $C$, the number of conflicts among teachers.

Each of the last $C$ lines holds two integers $i$ and $j$, meaning that FC teacher $i$ is in conflict with IC teacher $j$.

The limits are:

• $1 \le S \le 11000$
• $1 \le K_{FC}, K_{IC} \le 64$
• $1 \le N_{FC}, N_{IC}, T_{FC}, T_{IC} \le 1000$
• $1 \le D_{FC}, D_{IC} \le 8$
• $0 \le C \le T_{FC} \times T_{IC}$
• $1 \le d \le 6$ for every lab slot
• $8 \le h \le 20$ and $0 \le m \le 59$ for every lab slot
• $0 \le t < T_{FC}$ for an FC slot, and $0 \le t < T_{IC}$ for an IC slot
• $0 \le i < T_{FC}$ and $0 \le j < T_{IC}$ for every conflict

Two propositions for the same teacher never overlap.

Print one integer on a single line. Print 0 if no valid choice exists. Otherwise print the smallest number of days of the week that carry the starting times of the picked lab slots.