9666 - 银行家

你在一家银行工作，任务是帮助客户取出他们存放在保险箱里的金币。

银行里有 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 。

上海省选