#2584. 「SHOI2011」银行家

内存限制:128 MiB 时间限制:5000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: luyanaa

题目描述

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

输入格式

第一行有两个正整数: nnnmmmmmm 表示保险柜的数量, nnn 表示客户的数量。
第二行有 mmm 个非负正数,表示银行在开始营业前,第 111 号保险柜到第 mmm 号保险柜的金币数量。 接下来有 nnn 行,按照前来银行的顺序,依次描述了每个客户的情况。每行的开始都是一个非负整数 kkk ,接着有 kkk 个1到 mmm 之间的整数 a1,a2,,ak ,表示这个客户拥有 a1a_1a1 号、 a2a_2a2 号,直到 aka_kak 号保险箱的钥匙。最后还有一个非负整数 cic_ici ,表示他需要的金币数量。 输入保证所有出现在输入数据中的整数都不超过 100001000010000

输出格式

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

样例

样例输入 1

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

样例输出 1

7

样例输入 2

3 2
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

15

数据范围与提示

数据编号 数据限制
1 n≤30,m≤100 n\le 30,m\le 100n30,m100
2 n≤40,m≤50n\le 40,m\le 50n40,m50
3 n≤100,m≤400n\le 100,m\le 400n100,m400
4 n≤100,m≤400n\le 100,m\le 400n100,m400
5 n≤100,m≤400n\le 100,m\le 400n100,m400
6 n≤200,m≤500n\le 200,m\le 500n200,m500
7 n≤300,m≤800n\le 300,m\le 800n300,m800
8 n≤400,m≤1500n\le 400,m\le 1500n400,m1500
9 n≤500,m≤2000n \le 500,m\le 2000n500,m2000
10 n≤600,m≤2500n\le 600,m\le 2500n600,m2500