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 wants to buy only one copy of each present, even if he can achieve better price buying two copies of the same present. Sample input: 3 2 10 10 10 2 1 2 9 2 2 3 9 Sample output: 19 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. Though, as Peter wants exactly one copy of each present, presence of two second presents is not allowed, and we need to buy any deal and the remaining present for the full price, which leads to the answer 19 dollars.