15409번 - Majestic Gourmet University 다국어

The Majestic Gourmet University offers the prestigious Majestic International Cooking Degree to a large number of students each year.

Every student has to take two mandatory classes: French Cuisine (FC) and Italian Cuisine (IC), taught by two disjoint groups of teachers: FC teachers and IC teachers. These classes take the form of weekly “cooking labs”, and have limited capacity: K^FC students for FC labs and K^IC students for IC labs. To accommodate all students, there are therefore several lab instances for both FC and IC every week, each with its specific weekly timeslot and assigned teacher. One added complication is that some of the teachers are in open conflict with each other, disagreeing on teaching methods.

Every year, the heads of the FC and IC departments come up with a number of propositions for the weekly lab instances, and let Wise Bob from the Planning Office choose a subset of these propositions so that each student can have a valid timetable, which means:

• Every student must attend exactly one weekly FC lab and one weekly IC lab. Note that a student cannot attend two labs if their timeslots overlap or if they are separated by less than 5 minutes, to leave time for switching classrooms.
• Maximal capacities must be respected (at most K^FC students in an FC lab, and at most K^IC students in an IC lab).
• If an FC teacher A has a conflict with an IC teacher B, no student of a lab taught by A can attend a lab taught by B.
• Besides selecting weekly lab instances to ensure a proper lab assignment for all students, Wise Bob further wishes to ensure a maximum number of “free days” during the week. Accordingly, an optimal solution for Bob is one such that, regardless of the number of lab instances proposed, the starting time of their corresponding slots are spread over a minimum number of (not necessarily consecutive) days of the week.

Wise Bob asks for your help to figure out which lab slots to pick and how to dispatch students to these labs, so as to achieve an optimal solution.

Note that some teachers may not be appointed to any lab instances, while others may be in charge of several labs.

The input comprises the following lines all consisting of integers separated by single spaces:

• Line 1 consists of S, the number of registered students.
• Line 2 consists of N^FC, K^FC, D^FC and T^FC, where N^FC is the number of FC lab propositions, K^FC is the maximal capacity of each FC lab, D^FC is the duration (in hours) of each FC lab, and T^FC is the number of FC teachers.
• Each line from line 3 to line N^FC + 2 consists of the description of a proposed FC lab slot. FC slot i is described by four integers D_i^FC, H_i^FC, M_i^FC, T_i^FC, where D_i^FC is the day of the week, (H_i^FC, M_i^FC) is the starting time of the lab (hour, minutes) and T_i^FC is the FC teacher appointed.
• Line N^FC + 3 consists of N^IC, K^IC, D^IC and T^IC, where N^IC is the number of IC lab propositions, K^IC is the maximal capacity of each IC lab, D^IC is the duration (in hours) of each IC lab, and T^IC is the number of IC teachers.
• Each line from line N^FC + 4 to line N^FC + N^IC + 3 consists of the description of a proposed IC lab slot. IC slot i is described by four integers D_i^IC, H_i^IC, M_i^IC, T_i^IC, with the same meanings as for the FC slots.
• Line N^FC + N^IC + 4 consists of the number C of conflicts among teachers.
• Each of the last C lines consists of two integers i and j (0 ≤ i < T^FC, 0 ≤ j < T^IC), meaning that FC teacher i has a conflict with IC teacher j.

Limits

• 1 ≤ S ≤ 11 000 and 1 ≤ K^FC, K^IC ≤ 64;
• 1 ≤ N^FC, N^IC, T^FC, T^IC ≤ 1 000;
• 1 ≤ D^FC, D^IC ≤ 8;
• 0 ≤ C ≤ T^FC × T^IC;
• 1 ≤ D_i^FC, D_i^IC ≤ 6;
• 8 ≤ H_i^FC, H_i^IC ≤ 20 and 0 ≤ M_i^FC, M_i^IC ≤ 59;
• 0 ≤ T_i^FC < T^FC and 0 ≤ T_i^IC < T^IC.

Note that no two propositions for the same teacher may overlap.

The output consists of an integer on a single line. This integer is either (i) 0, if no solution exists, or (ii) the minimal number of days of the week that contain the starting time of slots in an optimal solution.