Problem D
Picture Day
The school for applied astrology has decided to take pictures of all their students. With moon phases being what they are, combined with Saturn’s position relative to Venus, they are forced to focus on cost.
In order to minimise cost, they have asked three photographers for their price and process. Photographer $A$ wants to take $G_ a$ group photos costing $a$ per photo. Photographer $B$ wants to take $G_ b$ group photos costing $b$ per photo. Photographer $C$ wants to take photos with one student in each photo, costing $c$ per photo.
Each student will be in exactly one of $A$’s groups and exactly one of $B$’s groups.
The three photographers are pretty flexible, so they will allow the school to choose some pictures from each if they want to.
What is the lowest price they have to pay so that each student will be in at least one picture?
Input
The first line of the input consists of a single integer
$N$, the number of
students in the school.
The second line consists of two space-separated integers,
$G_ a$, $G_ b$, representing the number of
groups for photographers $A$ and $B$.
The third line consists of the three space-separated integers
$a$, $b$, $c$, representing the prices of the
tree photographers.
The next $G_ a$ lines
represent photographer $A$’s groups, and consist of an
integer $G_{ai}$,
representing the number of students in that group, followed by
$G_{ai}$ space-separated
integers $S_ j$,
representing the student numbers in that group.
The next $G_ b$ lines
represent photographer $B$’s groups, and consist of an
integer $G_{bi}$,
representing the number of students in that group, followed by
$G_{bi}$ space-separated
integers $S_ j$,
representing the student numbers in that group.
Output
The output should be a single integer representing the cost of photographing all students at least once.
Limits
-
$1 \leq N \leq 1\, 000$
-
$1 \leq G_ a, G_ b \leq 50$
-
$1 \leq G_ a, G_ b \leq N$
-
$1 \leq G_{ai}, G_{bi} \leq N$
-
$1 \leq a, b, c \leq 1\, 000$
-
$1 \leq S_ j \leq N$
| Sample Input 1 | Sample Output 1 |
|---|---|
5 3 2 3 4 5 3 1 2 3 1 4 1 5 4 2 3 5 4 1 1 |
7 |
