# Practice on Toph

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

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

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 **C _{i}** 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 **C _{i}** (0 ≤ C

Then a binary matrix **A** of size **(N x M)** follows. The rows correspond to shops, and columns to items. If **A _{ij}** is

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.

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 |

21% Solution Ratio

fsshakkhorEarliest,

fsshakkhorFastest, 0.1s

JisangainLightest, 3.8 MB

YouKnowWhoShortest, 2746B

Login to submit