2943. 直硕面试

单点时限: 2.0 sec

内存限制: 256 MB

在今年的直升研究生面试中,ACM/ICPC 实验室的大四队员们遇到了一些问题:

面试 1:

老师:你对哪方面比较熟?

MJQ:我对算法设计很熟。

老师:哦,那很好啊。现在假设汇率已知,我能否通过不断兑换,使手里的货币升值?

MJQ:……

面试 2:

老师:你对哪方面比较熟?

ZZZ:数据挖掘。

老师:好的,那你给我讲一下贝叶斯信念网络。

ZZZ:……

面试 3:

老师:你对哪方面比较熟?

WWB:计算几何。

老师:不错嘛,那推导一下三维空间旋转矩阵。

WWB:……

在分析了几次不很理想的面试后,ACMer 们发现了一些规律:

  1. 老师都喜欢让你先说自己熟悉哪些方面,每个方面都能为你增加不同数量的印象分,当然你也可以不把自己熟悉的方面都说出来。

  2. 根据你的回答,老师会问与这些方面相关的细节知识点,你答不出就会扣除一定量的印象分(这里,我们极端假设你全答不上来)。

  3. 你最后的得分是:规律 1 中获得的印象分之和 减去规律 2 中扣除的印象分之和。

现在给出 ACMer 们熟悉的方面 和答不上来的知识点,以及它们之间的关系。请问他们如何选择熟悉的方面,才能使最后的印象分最高?

输入格式

第 1 行是一个整数 T 表示测试数据组数

接下来是 T 组测试数据,对于每组数据:

第 1 行有 2 个正整数 M 和 N(M,N<110)。M 是熟悉方面的数量,N 是答不上来的知识点数量。接下来的 M 行,每行是一个熟悉方面的有关数据。第一个数是该方面可以为 ACMer 增加的印象分;接着是与该方面有关的知识点的编号 V(1<= V <=N)。最后一行的 N 个数分别是答不出第 i 个知识点所要扣除的印象分 (同一个知识点只会被问一次)。

输出格式

每组测试数据,占一行,输出一个整数,即所能获得的最高印象分。

样例

Input
1
2 3
10 1 2
25 2 3
5 6 7
Output
17
Hint:第一个方面与1,2号知识点相关联,第二个知识点与2,3号知识点相关联。若ACMer回答熟悉第一个方面则最后得分10-5-6=-1;若回答熟悉第二个方面则最后得分25-6-7=12;若回答两个方面都熟悉,则最后得分10+25-5-6-7=17;若回答不熟悉任何方面则得0;所以最高得分是17。

2 人解决,19 人已尝试。

2 份提交通过,共有 39 份提交。

9.8 EMB 奖励。

创建: 8 年,1 月前.

修改: 2 年,4 月前.

最后提交: 5 年,2 月前.

来源: ECNU 2011 ACM/ICPC Selective Trials

题目标签