新手积分资助计划 - 宣传网站赢取积分(每点击一次奖20积分) - 政务大厅

How to earn more
Xiao Ming is an expert in computer science and technology, so he can get a lot of projects

every month. The projects always bring him a lot of money, now he is thinking how to earn

money as more as possible.

Every month he can get m projects, and each project Ai will bring him Xi yuan. Although Xiao

Ming is an expert, he still needs to hire some other guys to help him. Of course, the

employees are not as good as Xiao Ming, for they are just good at some single aspect. So,

they should work together to finish one project. There is a list shows the salary of m

employees, who are labeled from 0 to m-1. Xiao Ming only hires employees, in that list, and

he knows who will be needed by each project.If one employee is hired, he can join in several

projects.

Input

The first line is an integer c shows the number of cases. For each case, the first line has

two numbers m,n(m,n <=100), denoting that there is m projects and n employees on the

list.The second line has m integers, which are seperated by a single blank, the ith number

Ximeans the project Ai will bring Xiao Ming Xi yuan. Xi is less the 10000. The third line

has n integers, which are seperated by a single blank, the ith number Yimeans the employee

Bi will cost Xiao Ming Xi yuan. And the next m lines will show which part of the employees

will be needed by each project. Line i is a list of the employees, who are needed by project

Ai. In each line, first a number Zi shows the number of employees needed by this project.

And Zi labels of the emloyees follows, which are still seperated by a sigle blank.

Output

You should output a single integer shows the maximun money Xiao Ming can earn in a single

month. The money he can earn is equall to the money he can totally get minus the money he

totally cost. You should not leave any extra blanks at the end of each line.

Sample Input

1
3 5
30 40 43
55 17 23 22 11
3 0 1 2
3 1 2 3
2 2 1

Sample Output

Hint

If Xiao Ming can do less project to earn more money, he will certainly do that.

各位哥哥们，帮帮我啊！用C或C++都可以！
How to earn more
Xiao Ming is an expert in computer science and technology, so he can get a lot of projects