Description

You work at a bank, and your job is to help customers withdraw the gold coins stored in their safe deposit boxes.

There are $m$ safe deposit boxes in the bank. You cannot open these boxes because the keys are held by the customers. A customer may have keys to many boxes, and a box may also have keys held by multiple customers. This morning, the manager told you that you must receive $n$ customers in order (no two customers will arrive at the same time). You also know that the $i$-th customer will ask to withdraw $c_i$ gold coins. When a customer arrives, they will open all the boxes they can open and take $c_i$ coins from them (all coins are identical). If the total number of coins in these boxes is not enough, they will be unhappy. After taking as many coins as possible, they will go to your manager to complain that the bank’s service is terrible.

Of course, you do not want complaints to cost you your job, so you come up with a remedy: although each customer will close the boxes again when leaving, while they are taking coins, you can secretly adjust the numbers of coins in the opened boxes. For example, you can move the extra $5$ coins in box $1$ into box $2$, so that the next customer may be able to withdraw more coins.

Even with this method, it may still be impossible to satisfy all customers’ requests. However, you want to help customers withdraw as many coins as possible in total, so as to reduce their anger and keep this hard-earned job and salary.

Input Format

The first line contains two positive integers $m$ and $n$, where $m$ is the number of safe deposit boxes and $n$ is the number of customers.

The second line contains $m$ non-negative integers, representing the numbers of coins in boxes $1$ to $m$ before the bank opens. Then follow $n$ lines, describing each customer in the order they arrive. Each line starts with a non-negative integer $k$, followed by $k$ integers $a_1,a_2,\ldots,a_k$ between $1$ and $m$, indicating that the customer has the keys to boxes $a_1$, $a_2$, up to $a_k$. Finally, there is a non-negative integer $c_i$, indicating the number of coins they need. The input guarantees that all integers appearing in the input data do not exceed $10000$.

Output Format

Output one integer, the maximum possible total number of coins that all customers can withdraw. The input guarantees that the answer does not exceed $100000$.

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

7

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

5

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

15

Hint

Constraints

Translated by ChatGPT 5