CareerCup

Samu's Birthday is near so she had started planning a party for all of her friends. Being a kind and caring girl she calls each of her friend and asks for his/her favorite dish.Now each friend has own liking/disliking for different dishes.

A friend can only like or dislike a dish it means if we are having three dishes 1,2,3 then if a friend says that he likes Dishes 1 and 2 then its obvious that he dislikes Dish 3. So for each friend we are given a string of 1 and 0 where 1 shows that this person like this particular dish.

Now we are given that Samu has N friends and total of K dishes available to make her menu. Now Samu doesn't want to make any of her friend unhappy , After all its her birthday.

So she got confused on what dishes to count in menu and calls you for help. You need to find count of minimum dishes to order so that all of her N friends are happy which means everyone has at least one dish to eat in party.

Note : Its for sure that everyone has at least liking for one dish.

Input : Input will contain T test cases and each of the test case has following description :

First line of test case has N denoting the total number of friends and K denoting the total number of dishes available.Both separated by a space (Dishes are numbered from 1 to K) .

Then it is followed by N lines each of length K . Each of the N lines contains a string of 0 and 1 where if jth (1<=j<=K) value in ith line (1<=i<=N) is set 1 then it shows that dish

2. There is a maze of size n*n. Tom is sitting at (0,0). Jerry is sitting in another cell (the position of Jerry is input). Then there are k pieces of cheese placed in k different cells (k <= 10). Some cells are blocked while some are not. Tom can move to 4 cells at any point of time (left, right, up, down one position). Tom has to collect all the pieces of cheese and then reach to Jerry’s cell. You need to print the minimum no. of steps required to do so.


I know it is possible throgh dp but please provide me solution with approoch i am unable to solve it please