题目描述

Emmy 在一个养猪场工作。这个养猪场有 $M$ 个锁着的猪圈，但 Emmy 并没有钥匙。顾客会到养猪场来买猪，一个接着一个。每一位顾客都会有一些猪圈的钥匙，他们会将这些猪圈打开并买走固定数目的猪。 所有顾客有的钥匙和他们需要买猪的数量在事先都告诉了 Emmy，于是 Emmy 要订一个计划，使得卖出去的猪最多。 买卖的过程是这样的：一个顾客前来，并打开所有他可以打开的猪圈。然后 Emmy 从这些猪圈里牵出固定数目的猪卖给顾客（最多只能和顾客需要数相等），并可以重新安排这些开着的猪圈中的猪。 每个猪圈可以存放任意数目的猪。 写一个程序，使得 Emmy 能够卖出去尽可能多的猪。

输入格式

第一行有两个整数：$M$ 和 $N$，表示猪圈数和顾客数。 第二行有 $M$ 个整数 $C_1,C_2,\cdots,C_M$，表示每个猪圈初始时有多少猪。 接下来的 $N$ 行按照前来的次序描述了每一个顾客 $A,K_1,K_2,\cdots,K_A,B$。其中 $A$ 表示该顾客拥有的钥匙数，$K_1,\cdots,K_A$ 表示每个钥匙所对应的猪圈，$B$ 表示该顾客需要购买的猪的数目。

输出格式

一个数，表示最多能卖出的猪的数量。

输入输出样例

输入#1

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

输出#1

7

输入#2

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

输出#2

15

数据范围

对于所有数据，满足 $1\le M\le 10^3,1\le N\le 100,0\le C_i\le 1000$