Pig Catching

Jonghyuk works on a farm with M locked pig pens. Each pen initially contains some pigs, but Jonghyuk has no keys and cannot open any pen by himself.

One customer visits the farm each day. A customer has keys to some pens, opens every pen that their keys can open, and wants to buy a certain number of pigs.

Each day proceeds as follows.

1. When the customer arrives, every pen that can be opened with that customer's keys is opened.
2. Jonghyuk sells pigs to the customer. He may not sell more than the customer wants, but he may sell fewer.
3. After the sale, Jonghyuk may redistribute all remaining pigs arbitrarily among the pens that are currently open.

There is no limit on how many pigs a pen can contain. Determine the maximum total number of pigs Jonghyuk can sell over all customer visits.

The first line contains two integers M (1 <= M <= 1,000), the number of pig pens, and N (1 <= N <= 100), the number of customers. Pens are numbered from 1 to M, and customers are numbered from 1 to N in visiting order.

The second line contains M integers, where the i-th integer is the initial number of pigs in pen i. Each value is between 0 and 1,000 inclusive.

Each of the next N lines describes one customer in visiting order. The line for the i-th customer has the form A K_1 K_2 ... K_A B. This means the customer has keys to pens K_1, K_2, ..., K_A and wants to buy B pigs. A and B are nonnegative integers. If A is 0, the line contains no pen numbers before B.

Print one integer: the maximum number of pigs that can be sold.