The RUBIX Organizing Committee had planned to start publicizing their festival on the 29^th of Jan,2011. Due to a last minute mishap they lost the document which contained the information as to which volunteer would visit which college on what day!
They turned to their God Rubixius to help them out with the planning for the next week. They provide him with the number of volunteers and the maximum number of people each volunteer can attract per day. Being God Rubixius knows how many people will be present at each college each day. Rubixius has cast a spell which puts you in his shoes for this job. You have to help the OC by telling them the maximum number of people they can get each day along with the actual plan.

Input

The first line contains an integer T with the number of test cases. Each test case will have 2 integers N and C representing the number of volunteers and the number of colleges respectively. The next line will have N integers with the maximum each volunteer can attract per day. Then C lines follow each having 6 integers representing the number of people present at that college from Monday to Saturday respectively.

Output

For each case print a line with the maximum number of people the volunteers can get.

Input:
1
3 3
1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1

Output:
18


I believe that it is NP-Hard .  Can Anyone Throw some light !