마제스틱 미식 대학교

마제스틱 미식 대학교는 해마다 아주 많은 학생에게 마제스틱 국제 요리 학위를 준다.

모든 학생은 필수 과목 두 개를 듣는다. 프랑스 요리(FC)와 이탈리아 요리(IC)이고, 서로 겹치지 않는 두 교원 집단인 FC 교원과 IC 교원이 각각 맡는다. 두 과목 모두 주 1회 요리 실습으로 열리고 정원이 있다. FC 실습은 $K_{FC}$명까지, IC 실습은 $K_{IC}$명까지 받는다. 그래서 매주 FC 실습과 IC 실습이 여러 개 열리고, 실습마다 고유한 주간 시간대와 담당 교원이 정해진다. 성가신 사정이 하나 더 있다. 일부 교원은 교수법을 두고 의견이 갈려 서로 반목한다.

해마다 FC 학과장과 IC 학과장이 주간 실습 후보를 여럿 제안하고, 기획실의 밥이 그 후보 중 일부를 고른다. 모든 학생이 올바른 시간표를 받으려면 다음을 지켜야 한다.

• 학생은 주간 FC 실습 하나와 주간 IC 실습 하나를 정확히 하나씩 듣는다. 두 실습의 시간대가 겹치거나 사이 간격이 5분 미만이면 한 학생이 둘 다 들을 수 없다. 강의실을 옮길 시간이 필요하기 때문이다.
• 정원을 지켜야 한다. FC 실습은 $K_{FC}$명 이하, IC 실습은 $K_{IC}$명 이하다.
• FC 교원 A와 IC 교원 B가 반목하면, A가 맡은 실습의 학생은 B가 맡은 실습을 들을 수 없다.
• 밥은 쉬는 날도 최대한 많이 남기고 싶다. 올바른 선택 중에서 고른 실습의 시작 시각이 놓이는 요일 수가 가장 적어야 한다. 그 요일이 연속일 필요는 없다.

시간대는 한 주 전체를 기준으로 비교한다. 요일 번호가 $d$이고 $h$시 $m$분에 시작하는 실습은 $1440(d-1) + 60h + m$분부터 $1440(d-1) + 60h + m + 60L$분까지 이어진다. 여기서 $L$은 그 과목의 실습 시간이다. 한쪽이 끝난 뒤 5분 이상 지나서 다른 쪽이 시작할 때만 한 학생이 두 실습을 함께 들을 수 있다.

실습을 하나도 맡지 않는 교원이 있을 수 있고, 실습을 여러 개 맡는 교원도 있다.

밥을 도와 요일 수의 최솟값을 구하라.

모든 줄은 공백 하나로 구분한 정수로 이루어진다.

첫째 줄에 등록 학생 수 $S$가 주어진다.

둘째 줄에 $N_{FC}$, $K_{FC}$, $D_{FC}$, $T_{FC}$가 주어진다. 각각 FC 실습 후보 수, 모든 FC 실습의 정원, 모든 FC 실습의 진행 시간(시간 단위), FC 교원 수다.

다음 $N_{FC}$개 줄에 FC 실습 후보가 한 줄에 하나씩 주어진다. 각 줄은 정수 네 개 $d$, $h$, $m$, $t$로 이루어지고 각각 요일 번호, 시작 시각의 시, 시작 시각의 분, 담당 FC 교원 번호다.

다음 줄에 $N_{IC}$, $K_{IC}$, $D_{IC}$, $T_{IC}$가 IC에 대해 같은 뜻으로 주어진다.

다음 $N_{IC}$개 줄에 IC 실습 후보가 같은 형식으로 주어진다.

다음 줄에 교원 사이의 반목 수 $C$가 주어진다.

마지막 $C$개 줄에 정수 두 개 $i$와 $j$가 주어진다. FC 교원 $i$와 IC 교원 $j$가 반목한다는 뜻이다.

제한은 다음과 같다.

• $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$
• 모든 실습 후보에 대해 $8 \le h \le 20$, $0 \le m \le 59$
• FC 후보는 $0 \le t < T_{FC}$, IC 후보는 $0 \le t < T_{IC}$
• 모든 반목에 대해 $0 \le i < T_{FC}$, $0 \le j < T_{IC}$

같은 교원이 맡은 두 후보는 서로 겹치지 않는다.

한 줄에 정수 하나를 출력한다. 올바른 선택이 없으면 0을 출력한다. 있으면 고른 실습 후보의 시작 시각이 놓이는 요일 수의 최솟값을 출력한다.