Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Birthday Gifts

By fsshakkhor · Limits 1s, 512 MB

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.


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.


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


For each test case, print the maximum number of items Mr. Phil can buy.


3 5
1 1 2
4 6
1 1 2 2


Toph uses cookies. By continuing you agree to our Cookie Policy.