Bank Safe Coins Redistribution

You are working at a bank and your task is to help customers withdraw the coins stored in the safes. The bank has \(m\) safes, and you cannot open any safe by yourself because the keys are held by the customers. A customer may own keys to several safes, and a safe may have its key held by several customers. This morning, your manager informed you that you must serve \(n\) customers in sequence (no two customers arrive at the same time). You also know that the \(i\)th customer wants to withdraw \(c_i\) coins.

When a customer arrives, they will open all the safes for which they have keys. At that moment, you are allowed to redistribute the coins arbitrarily among the opened safes (for example, moving 5 extra coins from safe 1 into safe 2). Then the customer will withdraw \(c_i\) coins from these safes. If the total number of coins available among the opened safes is less than \(c_i\), the customer will take all the available coins and, after that, complain to your manager about the bank's service quality.

Your goal is to maximize the total number of coins withdrawn by the customers (thus, helping them get as many coins as possible) by optimal redistribution at each customer’s visit. Note that once a safe is opened for the first time, its coins become available, and coins can be moved freely among all safes opened by the current customer. However, safes that are not opened remain unchanged. Also, when a customer leaves, the safes are closed again, but the coins remain in their current safes.

Observation: Since you can redistribute coins arbitrarily among opened safes, the only coins available to satisfy a customer are those from safes being opened for the first time (i.e. coins that were previously locked away) together with any leftover coins from previous customers. The process is as follows:

1. Initially, each safe \(i\) (\(1 \le i \le m\)) contains \(a_i\) coins.
2. For each customer in order:
1. For every safe that the customer can open which has not been opened before, add its coins to an available pool.
2. The customer then withdraws \(\min(c_i, \text{pool})\) coins from the pool.
3. The remaining coins (if any) stay in the pool (assigned to the safes opened by this customer) for future customers.
3. The total coins withdrawn is the sum of coins taken by each customer.

Your task is to compute the maximum total number of coins that can be withdrawn by all customers with optimal redistribution.

inputFormat

The input begins with a line containing two integers \(m\) and \(n\) (the number of safes and the number of customers).

The second line contains \(m\) integers: \(a_1, a_2, \ldots, a_m\), where \(a_i\) is the number of coins initially in safe \(i\).

Then \(n\) lines follow, one for each customer in order. Each of these lines begins with two integers: \(c_i\) (the number of coins the customer wants to withdraw) and \(k_i\) (the number of safes the customer can open). This is followed by \(k_i\) integers representing the 1-indexed indices of the safes that this customer can open.

outputFormat

Output a single integer denoting the maximum total number of coins withdrawn by all customers.

sample

3 3
5 3 10
6 2 1 2
7 2 2 3
5 1 1

18