P4638 [SHOI2011] 银行家

你在一家银行工作，任务是帮助客户取出他们存放在保险箱里的金币。 银行里有 $m$ 个保险箱，你没有办法打开这些保险箱，因为钥匙都在客户的手里。一个客户可能有很多个保险箱的钥匙，一个保险箱的钥匙也可能被多个客户拥有。今天早上，经理已经告知，你需要按照顺序接待 $n$ 个客户（任何客户都不会同时到场），你也知道，第 $i$ 个客户会要求取走 $c_i$​​ 枚金币。每个客户来到银行的时候，会打开所有他能打开的保险箱，然后从中取走 $c_i$​​ 枚金币（任何金币都没有区别），如果这些保险箱里的金币数量不足 ，他会感到不高兴，在取走尽量多的金币之后，到你的经理那里去投诉你们银行的服务质量太差了。 你当然不希望“上帝”的投诉让你丢了工作，于是想到了个补救的办法：虽然每个客户走的时候都会把保险箱重新关上，但是你可以在他取金币的时候，偷偷地调整被打开的保险箱里的金币数量，譬如说把 $1$ 号保险里多余的 $5$ 枚放到 $2$ 号里，这样说不定下个客户来的时候，就能取到更多的金币了。 尽管有这样的方法，还是可能没法完成所有客户的要求。然而，你希望，尽量帮助客户取走更多的金币，这样才能消除他们的怒气，保住这份来之不易的工作和薪水。

第一行有两个正整数： $m$ 和 $n$ ， $m$ 表示保险柜的数量， $n$ 表示客户的数量。 第二行有 $m$ 个非负正数，表示银行在开始营业前，第 $1$ 号保险柜到第 $m$ 号保险柜的金币数量。 接下来有 $n$ 行，按照前来银行的顺序，依次描述了每个客户的情况。每行的开始都是一个非负整数 $k$ ，接着有 $k$ 个 $1$ 到 $m$ 之间的整数 $a_1,a_2,…,a_k$ ，表示这个客户拥有 $a_1$​​ 号、 $a_2$ 号，直到 $a_k$​​ 号保险箱的钥匙。最后还有一个非负整数 $c_i$​​ ，表示他需要的金币数量。 输入保证所有出现在输入数据中的整数都不超过 $10000$ 。

输出只需要一个整数，表示所有客户可以取走的金币总数的最大值。 输入保证答案不会超过 $100000$ 。

### 数据范围 测试点编号 .|n$\le$ .|m$\le$ . -|-|- 1|30|100 2|40|50 3|100|400 4|100|400 5|100|400 6|200|500 7|300|500 8|400|1500 9|500|2000 10|600|2500