Problem I
Waif Until Dark

“Waif Until Dark” is a daycare center specializing in children of households where both parents work during the day. In order to keep the little monsters …that is, darlings …occupied, the center has a set of toys that the kiddies can play with. Some of these toys belong to one of several categories – sports toys, musical toys, dolls, etc. In order to save wear and tear on these types of toys, the teachers allow only certain numbers of toys of each category to be used during playtime. Of course, kids being kids, not all of the toys are liked by everyone, so sometimes it’s difficult to make sure every kid has a toy they like. Given all of these constraints, the CEO of Waif has come to you to write a little program to determine the maximum number of these monsters (let’s be honest here) who can be satisfied.


Input starts with a line containing three integers $n$ $m$ $p$ indicating the number of children, the number of toys and the number of toy categories ($1 \leq n,m \leq 100, 0 \leq p \leq m$). Both children and toys are numbered starting at $1$. After this line are $n$ lines of the form $k$ $i_1$ $i_2$$i_ k$ ($1 \leq k, i_1, i_2, \ldots , i_ k \leq m$); the $j^{th}$ of these lines indicates that child $j$ is willing to play with toys $i_1$ through $i_ k$. Next are $p$ lines of the form $l$ $t_1$ $t_2$$t_ l$ $r$ ($1 \leq r \leq l \leq m, 1 \leq t_1, t_2, \ldots , t_ l \leq m$); the $j^{th}$ of these lines indicates that toys $t_1$ through $t_ l$ are in category $j$ and that at most $r$ of these toys can be used. Toys can be in at most one category and any toy not listed in these $p$ lines is not in any toy category and all of them can be used. No toy number appears more than once on any line.


Display the maximum number of children that can be satisfied with a toy that they like, provided that each toy can be used by at most one child.

Sample Input 1 Sample Output 1
4 3 1
2 1 2
2 1 2
1 3
1 3
2 1 2 1

Please log in to submit a solution to this problem

Log in