By Marcio T. I. Oshiro Brazil
St. Petersburg is known as the capital of the Russian beer and home to several major breweries. They say the water quality of the city is responsible for a beer of excellent quality. Besides traditional plants such as Heineken, some local brands are highlighted, as Tinkoff and Baltika. Also produced in the city are some of the best vodkas in the world. The oldest, called Liviz, date from 1897. This distillery produces excellent quality vodkas, measured by international standards. Interestingly, some types of vodkas, when eaten together, end up having, according to experts, much better flavor. Thus, some types of vodka are collected in categories that, when fully purchased by the consumer, bring an added benefit measured according to international quality standards. Each has an associated price vodkas, and your task is to find a purchase that maximizes the total benefit minus the cost of purchased vodkas.
Rewriting each vodka has a cost Cj and M are different categories, each with a benefit Bi. One benefit is only computed if all kinds of vodka comprising the category are acquired. A single bottle of vodka can participate in more than one category to compute the benefit. Your task is to determine which types of vodka purchase in order to maximize the sum of the benefits minus the cost of purchased items purchased. You can assume that Russia was to have enough money to buy all kinds of vodka produced by Liviz (yeah!! :D).
The input consists of various instances and ends with the end of file (EOF). The first line in each instance contains two integers N (1 ≤ N ≤ 600) and M (1 ≤ M ≤ 400) representing respectively the number of different types of vodka sales and the number of existing categories. The types of vodka are identified by numbers 1 to N of categories of numbers from 1 to M.
The next line contains N integers, Cj (1 ≤ Cj ≤ 1000) for (1 ≤ j ≤ N), separated by space, corresponding to the cost of vodka j. On the next line there are M integers, Pi (1 ≤ Pi ≤ N), separated by space, indicating how many different types of vodkas composes category i. Each of the following M lines describes a category starting with a integer Bi (1 ≤ Bi ≤ 1000) for (1 ≤ i ≤ M), indicating their benefit, followed by the types of vodka that compose it, separated by spaces.
For each instance print, on a single line, the highest value that can be obtained from the sum of the benefits of the categories acquired minus the cost of purchased types of vodkas.
|Sample Input||Sample Output|