Problem Description

You work at a bank, tasked with helping customers withdraw their gold coins stored in safes.

The bank has $m$ safes, which you cannot open as the keys are in the customers' hands. A customer may have keys to multiple safes, and a safe's key may be owned by multiple customers. This morning, the manager informed you that you need to serve $n$ customers in order (no customers will arrive simultaneously), and you know that the $i$-th customer will request to withdraw $c_i$ gold coins. When a customer arrives at the bank, they will open all the safes they can access and then take $c_i$ gold coins from them (all coins are indistinguishable). If there are not enough coins in these safes, the customer will be unhappy and, after taking as many coins as possible, will complain to your manager about the poor service quality of the bank.

You certainly do not want to lose your job due to "God's" complaints, so you come up with a remedy: although each customer will close the safes when they leave, you can secretly adjust the number of coins in the opened safes while they are taking coins, for example, moving 5 extra coins from safe 1 to safe 2, which might allow the next customer to take more coins.

Even with this method, it may still be impossible to meet all customers' requests. However, you hope to help customers take as many coins as possible to appease their anger and keep this hard-earned job and salary.

Input Format

The first line contains two positive integers: $m$ and $n$, where $m$ represents the number of safes and $n$ represents the number of customers.

The second line contains $m$ non-negative integers, indicating the number of gold coins in each safe from safe 1 to safe $m$ at the start of business. The following $n$ lines describe each customer in the order they arrive at the bank. Each line starts with a non-negative integer $k$, followed by $k$ integers between 1 and $m$, $a_1, a_2, \ldots, a_k$, indicating that this customer has keys to safes $a_1, a_2, \ldots, a_k$. Finally, there is a non-negative integer $c_i$, indicating the number of coins they need. The input guarantees that all integers in the input data do not exceed $10000$.

Output Format

The output should be a single integer, representing the maximum total number of coins that all customers can take. The input guarantees that the answer will not exceed $100000$.

Sample Input and Output

Input Sample #1

3 3
3 1 10
2 1 2 2
2 1 3 3
1 2 6

Output Sample #1

7

Input Sample #2

2 3
2 3
2 1 2 1
1 2 2
1 2 2

Output Sample #2

5

Input Sample #3

6 6
6 3 2 0 1 3
2 1 2 0
1 3 3
1 1 1
2 2 3 8
2 4 5 2
2 4 6 6

Output Sample #3

15

Notes

Data Range

见题面 Input 部分

见题面 Output 部分