Pig Catching

Time limit1sMemory limit256 MB

Summary
Given pig pens opened by daily keyed customers who buy up to a limit and pigs can be freely redistributed among opened pens, find the maximum total pigs sellable over all visits.
Level

Hard8 of 10

Topics
Union-find, Graph, Greedy
Solved
No attempts yet

Problem

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.

Input

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.

Output

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

Examples3

  1. Example 1

    Input
    3 3
3 1 10
2 1 2 2 
2 1 3 3
1 2 6
    Expected output
    7

  2. Example 2

    Input
    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
    Expected output
    15

  3. Example 3

    Input
    11 5
1 2 2 1 0 2 4 1 1 1 2
5 1 2 3 4 5 3
4 1 2 6 7 5
2 3 8 1
3 3 6 11 5
3 8 9 10 3
    Expected output
    17