406808: GYM102562 I Mafia

Memory Limit:256 MB Time Limit:0 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

I. Mafiatime limit per test0.5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Peter the gangster is the new mob boss in the city and wants to grow his affairs as fast as possible. The best way to do that is by collection some pizzo (protection taxes) from influential people that are already protected by other mob bosses. Peter can establish friendship relations with any mob for some amount of money. One person may have multiple mobsters protecting him. To be able to get money from a person, Peter needs first to be friend with the mobsters protecting him.

Given for each person the amount of money he is able to pay and for each mobster the amount of money requested for his friendship, find the maximum amount of money Peter can collect.

Input

The first line of the input contains 2 numbers, $$$1 \leq N \leq 100$$$ (the number of mob bosses) and $$$1 \leq M \leq 100$$$ (the number of influential people).

The next line contains $$$N$$$ numbers representing the amount of money each mob requests for his friendship.

The next line contains $$$M$$$ numbers representing the amount of money each person is able to pay.

The next $$$M$$$ lines will contain, for each person $$$i$$$, the number $$$k_i$$$, the number of mobsters protecting person $$$i$$$, followed by $$$k_i$$$ numbers representing the mobsters protecting person $$$i$$$.

Any amount of money in the input is a positive integer $$$\leq 5000$$$.

Output

The output should contain a number containing the maximum amount of money Peter can collect.

ExamplesInput
5 5
7 10 3 1 6
5 2 3 9 7
1 3
1 4
1 2
3 1 2 3
1 4
Output
10
Input
5 8
19 15 18 7 8
13 9 8 5 8 5 10 5
1 5
3 1 2 3
2 1 3
1 4
2 1 5
2 1 5
4 1 2 3 5
1 1
Output
5

加入题单

上一题 下一题 算法标签: