2237

2237. 猪

题目

米尔克在一家养猪场工作，该养猪场共有 $M$ 个上了锁的猪舍。

由于米尔克没有钥匙，所以他无法打开任何猪舍。

顾客们顺次来到了养猪场，不会有两个顾客同一时间过来。他们中的每个人都有一些猪舍的钥匙，并且想买一定数量的猪。

米尔克每天一大早就可以得到计划在当天来到农场的客户的所有数据，以便他制定销售计划，从而最大限度地提高出售生猪的数量。

更准确的说，过程如下：

1. 顾客到达养猪场，将所有他有钥匙的猪舍的大门全部打开，米尔克从所有未上锁的猪舍中挑选一定数量的猪卖给该顾客。
2. 如果米尔克愿意，他还可以给未上锁的猪舍里剩下的猪重新分配位置。
3. 在每个顾客到达之前，会将上一个顾客打开的猪舍全部关闭。

每个猪舍中都可以放置无限数量的猪。

请你编写一个程序，计算他当天可以出售的生猪的最大数量。

输入格式

第一行包含两个整数 $M$ 和 $N$，表示猪舍数量以及顾客数量。

猪舍编号从 $1$ 到 $M$，顾客编号从 $1$ 到 $N$。

第二行包含 $M$ 个整数，表示每个猪舍初始猪的数量（不少于 $0$，不超过 $1000$）。

接下来 $N$ 行，描述所有顾客的信息（第 $i+2$ 行描述第 $i$ 个到来的顾客的信息）：每行首先包含一个整数 $A$，表示该顾客拥有的钥匙数量，然后包含 $A$ 个整数 $K_1,K_2,…,K_A$，表示钥匙对应的猪舍编号（按升序给出），最后包含一个整数 $B$，表示他想购买的猪的数量。

输出格式

输出可以出售的生猪的最大数量。

数据范围

$1 \le M \le 1000$,

$1 \le N \le 100$,

$0 \le A \le M$,

$1 \le K_i \le M$,

$0 \le B \le 10000$

输入样例：

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

输出样例：

7

题解