Emmy卖猪pigs

Emmy 在一个养猪场工作。这个养猪场有 $M$ 个锁着的猪圈，但 Emmy 并没有钥匙。

顾客会到养猪场来买猪，一个接着一个。每一位顾客都会有一些猪圈的钥匙，他们会将这些猪圈打开并买走固定数目的猪。所有顾客拥有的钥匙和他们需要买猪的数量在事先都告诉了 Emmy，于是 Emmy 要订一个计划，使得卖出去的猪最多。

买卖的过程是这样的：一个顾客前来，并打开所有他可以打开的猪圈；然后 Emmy 从这些猪圈里牵出固定数目的猪卖给顾客（最多只能和顾客需要数相等），并可以重新安排这些开着的猪圈中的猪。

每个猪圈可以存放任意数目的猪。

写一个程序，使得 Emmy 能够卖出去尽可能多的猪。

输入格式

第一行有两个整数 $M$ 和 $N$，表示猪圈数和顾客数。

第二行有 $M$ 个整数，表示每个猪圈初始时有多少猪。

接下来的 $N$ 行按照前来的次序描述了每一个顾客，每行的格式如下：

A K1 K2 ... KA B

其中 $A$ 表示该顾客拥有的钥匙数，$K_1, \dots, K_A$ 表示每个钥匙所对应的猪圈，$B$ 表示该顾客需要购买的猪的数目。

输出格式

仅包含一个整数，即最多能卖出去的猪的数目。

样例输入

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

样例输出

7

样例解释

三个猪圈初始分别有 $3, 1, 10$ 头猪。

1. 第一位顾客打开猪圈 $1, 2$，共 $4$ 头猪，卖出 $2$ 头；把剩下的 $2$ 头全部安排到猪圈 $2$，此时三个猪圈为 $0, 2, 10$；
2. 第二位顾客打开猪圈 $1, 3$，共 $10$ 头猪，卖出 $3$ 头；
3. 第三位顾客打开猪圈 $2$，只有 $2$ 头猪，虽然想买 $6$ 头，但只能卖出 $2$ 头。

总共卖出 $2+3+2=7$ 头猪。

数据范围

• $1\le M\le 1000$；
• $1\le N\le 100$。

来源与许可

本题题面与测试数据整理自 BZOJ 1280。

样例 1

输入

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

输出

7