The ACM Problems Problem (acmproblems.X) Farmer Matt has only a few days left to solve ACM problems this semester! There is a list of P (1 <= P <= 1000) problems that have been assigned, and each of the problems has a (potentially different) point-value, ranging from 1 to 10,000 points, all of which will contribute to FM's final total of ACM problem points in the class. Fortunately, FM has a large herd of cows willing to help him solve these ACM problems. Unfortunately, they require a variety of sources of caffeine in order to do so. FM can purchase up to T (1 <= T <= 1000) different types of caffeine, each of which will spur different cows to help work on ACM problems! Caffeine type #1, for example, is a Starbucks Moochachino; caffeine type #42 is coffee-flavored soy ice cream (the cows don't do dairy). Because FM does not have funds to purchase caffeine sources, he has decided to take advantage of the ACM class's points-for-products plan. This plan allows FM to obtain caffeinated products in exchange for ACM problem points. Each caffeine type can be obtained in exchange for some designated amount of ACM problem points. For example, caffeine type #1 might cost 2 ACM problem points; caffeine type #42 might cost 10 ACM problem points. FM wants to know how to maximize his total ACM problem points, calculated as all of the points earned as a result of solving ACM problems minus the points used in "purchasing" types of caffeine for the cows who will help solve those problems. Each type of caffeine, once purchased, provides enough to satisfy any and all of the cows who prefer that type. What is the maximum total number of ACM problem points FM can earn? PROBLEM NAME: acmproblems INPUT FORMAT: * Line 1: Two space-separated integers: T and P, where T is the number of types of caffeine available and P is the number of problems to be solved * Lines 2 to T+1: Line i+1 is a single integer that is the number of ACM problem points needed to obtain caffeine type i * Lines T+2 to T+P+1: Each of these lines contains several space-separated integers that describe each ACM problem that can be solved: * Each line's first integer is the number of points the ACM problem is worth. * Each line's second integer is the number, N, of caffeine sources needed to recruit the necessary cows to help solve the problem. * The next N integers on each line are unique: they indicate _which_ sources of caffeine are needed to solve that line's ACM problem. SAMPLE INPUT: 4 3 2 3 4 5 3 2 1 2 4 3 1 3 4 7 2 2 3 Explanation of sample input: There are four types of caffeine and three problems to solve. The first type of caffeine costs 2 ACM points; the second costs 3 ACM points; the third costs 4 ACM points; the fourth costs 5 ACM points. The final three lines describe the three ACM problems to be solved. For example, the first ACM problem is worth 3 points, requires 2 sources of caffeine to solve: caffeine types #1 and #2. The second ACM problem is worth 4 points and requires 3 sources of caffeine to solve: types #1, #3, and #4. OUTPUT FORMAT: * Line 1: A single integer that is the maximum number of points FM can earn. Note that this can not be less than zero. SAMPLE OUTPUT: 1 Explanation of sample output: FM spends 9 points to obtain caffeine types #1, #2, and #3. This allows him to solve ACM problems worth 3 points and 7 points. As a result, FM nets 10-9 == 1 point in this case.