Tea Break
InterviewTime limit2sMemory limit256 MB
Each of n employees has a set of favorite tea kinds, and given a_i bags of each kind, find how many days everyone can drink a favorite tea.
- Level
Medium5 of 10
- Topics
- Binary search, Greedy, Implementation, Brute force
- Solved
- No attempts yet
Problem
n people work in one department of a large organization. Like almost all employees of this organization, they enjoy drinking tea during breaks from work. They are disciplined enough to take exactly one break a day, during which they drink tea. To make this break as pleasant as possible, each employee of the department drinks tea of one of their favorite kinds. On different days an employee may drink different kinds of tea. For convenience, the kinds of tea are numbered from 1 to m.
Recently the employees of the department bought a large set of tea bags containing a1 bags of tea kind 1, a2 bags of tea kind 2, ..., am bags of tea kind m. Now they want to know the maximum number of days the purchased set can last so that on each of those days every employee gets a tea bag of one of their favorite kinds.
Each employee of the department drinks exactly one cup of tea a day, brewed from one tea bag. Tea bags are not brewed twice.
Input
The first line contains two integers n and m (1 ≤ n, m ≤ 50). The second line contains m integers a1, ..., am (1 ≤ ai ≤ 106 for every i from 1 to m).
The next n lines follow. The i-th of these lines describes the favorite kinds of the i-th employee of the department and has the following format: first a positive integer ki, the number of favorite kinds of tea of this employee, then ki distinct integers from 1 to m, the numbers of these kinds.
Output
Print one integer, the maximum number of days sought.