Peter wants to buy N presents for the Thanksgiving. He know the price of each
present he wants to buy. Also, as it usually happens before Thanksgiving, 
shops have a lot of deals. For example, the price of the toy pig is ten dollars,
the price of the toy donkey is 12 dollars, but when you buy both of them, you
pay only 20 dollars. Peter visited all the shops near his house and collected
all the data about all the deals. Now he wants to but all the presents he wants
and pay as little as possible.

Input data specification:
First line of the input contains two numbers: number of presents Peter wants to
buy N and number of deals M. Second line contains N space separated numbers -
price of each present alone. Then M lines follow, each in the format
k P1 P2 ... Pk C
Where k is number of presents in the corresponding deal
P1, P2 ... Pk are 1-based numbers of the presets,
and C is price of the deal. This means, that you can buy presents P1, P2 ... Pk
and pay only C dollars.

Output data specification:
Output one number - the minimum amount of money Peter needs to pay to buy all
the presents. Note, that Peter can buy more that one copy of the same present, if
it allows him to achieve better price.

Sample input:
3 2
10 10 10
2 1 2 9
2 2 3 9

Sample output:
18

Sample description:
Here we have three presents each with price 10 dollars, and two deals. First deal
offers first and second presents for only 9 dollars (which is more than 50% discount)
and the second deal offers second and third presents for only 9 dollars.
The best way to buy both presents is to buy both deals. In this case you will have
first present, two second presents and the third present for only 18 dollars. As
Peter has at least one copy of each present, Peter doesn't worry about having one
extra second present. And it is impossible to achieve price better than 18 dollars.