Today is Luke's birthday. Mr. Phil Dunphy (Luke's father) has thrown a birthday party for him and decided to buy some gifts for Luke. So he searched on the internet and collected the following information.
There are total M different types of gift items in the city shops. The item types are numbered from 1 to M. There are total N shops where these items can be found. But a single shop may not contain all type of items. He has the list of items each shop has.
Mr. Phil has managed N assistants to help him. He will send each of his assistant to exactly one shop. Also no shop should be assigned to more than one assistant. The i'th assistant can buy at most Ci items from their assigned shop. They can not buy item from any other shop except their assigned one. Each assistant can buy one instance of each type of item. Also no two assistant can buy the same type of item.
Mr. Phil wants to assign shops to his assistants in such a way that he can buy maximum number of gifts.
Input
First line contains an integer T, denoting the number of testcases.
In each test case, the first line contains two integers N and M.
The second line contains N integers Ci (0 ≤ Ci ≤ M) - denoting the capacity of items the i'th assistant can buy.
Then a binary matrix A of size (N x M) follows. The rows correspond to shops, and columns to items. If Aij is 1, then the j'th item is available in the i'th shop, otherwise unavailable.
Scoring
Subtask 1 (20 Points): 1 ≤ T ≤ 15 N = 2 1 ≤ M ≤ 100000
Subtask 2 (40 Points): 1 ≤ T ≤ 5 3 ≤ N ≤ 5 1 ≤ M ≤ 1000
Subtask 3 (40 Points): 1 ≤ T ≤ 5 3 ≤ N ≤ 5 1 ≤ M ≤ 100000
Output
For each test case, print the maximum number of items Mr. Phil can buy.
Samples
| Input | Output |
|---|---|
1 3 5 1 1 2 10010 00110 01010 | 4 |
| Input | Output |
|---|---|
1 4 6 1 1 2 2 000101 100011 000111 111100 | 6 |
