Party
Time limit2sMemory limit128 MB
Given N cooks each able to bring at most K dishes from foods they know how to cook and per-food capacity limits, compute the maximum total dishes preparable via max flow.
Problem
N people are preparing food for a party. Food types are numbered from 1 to D. Each person may bring only food types they know how to cook, and each person may bring at most K plates. The same person cannot bring two or more plates of the same food type.
Each food type also has an upper limit on how many plates of that type may be prepared. Determine the maximum total number of plates that can be prepared while satisfying all limits.
Input
The first line contains N, K, and D (3 <= N <= 200, 1 <= K <= 5, 5 <= D <= 100).
The second line contains D integers. The i-th integer is the maximum number of plates allowed for food type i. Each value is an integer between 0 and N, inclusive.
Each of the next N lines describes one person. A line starts with an integer Z (1 <= Z <= D), followed by Z integers: the food types that person can cook.
Output
Print the maximum number of plates that can be prepared.