A85773.「SHOI2011」银行家

省选/NOI-

通过率：0%

时间限制：5.00s

内存限制：128MB

题目描述

你在一家银行工作，任务是帮助客户取出他们存放在保险箱里的金币。
银行里有 $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 , \dots , a_k $ ，表示这个客户拥有 $a_1$ 号、 $a_2$ 号，直到 $a_k$ 号保险箱的钥匙。最后还有一个非负整数 $c_i$ ，表示他需要的金币数量。
输入保证所有出现在输入数据中的整数都不超过 $20000$ 。

输出格式

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

输入输出样例

输入#1
```
3 3
3 1 10
2 1 2 2
2 1 3 3
1 2 6
```
输出#1
```
7
```
输入#2
```
2 3
2 3
2 1 2 1
1 2 2
1 2 2
```
输出#2
```
5
```

输入#3

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

输出#3

说明/提示

数据编号	数据限制
1	$ n\le 30,m\le 100$
2	$n\le 40,m\le 50$
3	$n\le 100,m\le 400$
4	$n\le 100,m\le 400$
5	$n\le 100,m\le 400$
6	$n\le 200,m\le 500$
7	$n\le 300,m\le 800$
8	$n\le 400,m\le 1500$
9	$n \le 500,m\le 2000$
10	$n\le 600,m\le 2500$

首页