说明

某理工学院的实验室计划了一系列的实验项目$E＝{E_1，E_2，…，E_m}$,这些实验需要使用的全部仪器集合$I＝{I_1，I_2，…，I_n}$。每个实验需要的仪器是全部仪器集合的子集。配置仪器Ij需要的费用为cj，实验Ei产生的经济效益为pi美元。需要设计一个有效的算法，确定要进行哪些实验，使最终得到的经济效益减去需要配置的仪器费用后得到的净收益最大。

输入格式

第一行是一个整型数$C(C<100)$表示共有$C$组测试数据。

每组测试数据第一行输入实验数$m$和仪器数$n（1<=m,n<=100）$。

接下来$m$行，输入实验产生的效益$w$和该实验需要的仪器编号$c_i$（为0结束）。$（1<=w<=100,1<=c_i<=m）$。

最后一行$n$个数，输入所有仪器的费用cost（1<=cost<=100）。

输出格式

对于每一组输入，输出最大净收益。

每组的输出占1行。

样例

1
5 15
20 2 4 8 11 0
38 1 5 14 0
25 2 5 7 15 0
17 1 3 6 9 13 0
22 10 12 15 0
2 7 4 8 10 1 3 7 5 9 15 6 12 17 8

23

来源

《趣学算法》7.8节