Cow Carnival carnival.X
Farmer Ran wishes to take one or more of his N (1 <= N <= 100)
cows convenientily numbered 1..N to the cow carnival. The cost to
take a cow to the carnival (1..200,000) depends on the cow's weight
and the amount of snacks she consumes (cows love deep-fried Oreos).
A number M (1 <= M <= 100) of rich cow-fans sometimes sponsors the
carnival. Cow-fan i has a list of his favorite cows, and will pay
a fixed amount of sponsor money S_i (1 <= S_i <= 1,000,000) if all
of his favorite cows are present in the carnival.
Naturally, FR wants to maximize profit (even if it's negative),
which is total money he gets from cow-fans minus total money he has
to pay for cows' expenses. How much profit can he make?
PROBLEM NAME: carnival
INPUT FORMAT:
* Line 1: Two space-separated integers: N and M
* Lines 2..N+1: Line i+1 contains a single integer that is the cost to
take cow i to the carnival
* Lines N+2..N+M+1: Line i+N+1 contains a list of space-separated
integers that describes the sponsor money and favorite cow
list of cow-lover i. The first integer is S_i. The second
integer is the number of cows NC_i in his list. The subsequent
NC_i integer(s) are the cow numbers of the favorite cows.
SAMPLE INPUT:
3 2
10
5
3
20 2 1 2
7 2 1 3
OUTPUT FORMAT:
* Line 1: A single integer which is the maximum profit FJ can gain.
SAMPLE OUTPUT:
9
OUTPUT DETAILS:
Selecting all the cows has cost: 10+5+3=18 On the other hand in this case
cow-lovers will pay FJ: 20+7=27
And the profit is 27-18=9