1

# Placment Of students

Difficulty: EASY
Avg. time to solve
15 min
Success Rate
90%

Problem Statement
Suggest Edit

#### The data about the set of favourable jobs is given in the form of an m*n binary matrix named as ‘mat’. I.e for M students we have M rows each having N integers. Now for example if the first candidate is interested in job1 the value of mat[i][j] will be 1 otherwise it will be 0.Note that it is possible that a single candidate is interested in multiple jobs but he can take up only one of the job out of his favourable jobs.

##### Note:
``````1. No need to print anything, just return the maximum number of people that can get their favourable job.
2. There is no priority in jobs , i.e all favourable jobs are equally favourable to the candidate
``````
##### Input Format:
``````The first line of input contains an integer ‘T’ representing the number of test cases. Then the test cases follow.

The first line of each testcase contains 2 space-separated integers ‘m’ and ‘n’ which denote the number of applicants and number of jobs respectively.

The next ‘m’ lines have ‘n’ space separated binary numbers which denote the favourable jobs of each applicant.
``````
##### Output Format:
``````For each test case, return a single integer denoting the maximum number of applicants that got their favourable jobs

The output for each test case is in a separate line.
``````
##### Constraints:
``````1 <= T <= 100
1 <= N*M <= 3000

Where ‘T’ is the number of test cases, and ‘m’*’n’ is the number of elements in the matrix

Time Limit: 1sec
``````
##### Sample Input 1:
``````2
3 2
1 0
0 1
0 0
4 4
0 0 1 1
1 1 1 1
0 0 0 1
1 0 0 0
``````
##### Sample Output 1:
``````2
4
``````
##### Explanation of Sample Input 1:
``````Test Case 1:

We see that we have 3 candidates and 2 jobs.

Candidate 1 wants jobs 1 only
Candidate 2 wants job 2 only
Candidate 3 does not like any job

So, with this given arrangement, we can have that candidate 1 gets job1 and candidate 2 gets job 2. So we placed 2 candidates. Hence we return 2.

Test Case 2:

We have 4 candidates and 4 jobs

Candidate 1 wants jobs 3 or jobs 4.

Candidate 2 wants any of the 4 jobs (pretty desperate)

Candidate 3 wants only job 4

Candidate 4 wants only job 1

So with this arrangement, we can have candidate 1 with job 3, candidate 2 with job 2 candidates 3 with job 4 and candidate 4 with job 1.

Hence we placed all the candidates, hence we return 4.
``````
##### Sample Input 2:
``````2
3 4
1 1 1 1
1 1 1 1
1 1 1 1
6 6
0 1 1 0 0 0
1 0 0 1 0 0
0 0 1 0 0 0
0 0 1 1 0 0
0 0 0 0 0 0
0 0 0 0 0 1
``````
##### Sample Output 2:
``````3
5
``````