Maximum Enrollment of Students in Courses

Given a binary matrix \(P\) of size \(n \times m\), where the element \(P_{ij}\) is 1 if the \(i\)-th student is interested in the \(j\)-th course and 0 otherwise, determine the maximum number of students that can enroll in a course. Each student can enroll in at most one course and each course can accept at most one student. This problem can be modeled as a bipartite matching problem. One way to express the objective using LaTeX is: $$\max \sum_{i=1}^{n} \sum_{j=1}^{m} x_{ij}$$ subject to suitable allocation constraints.

inputFormat

The input is provided on standard input (stdin) in the following format:

• The first line contains two integers \(n\) and \(m\), representing the number of students and courses respectively.
• Each of the following \(n\) lines contains \(m\) space-separated integers (each 0 or 1), describing the interest matrix \(P\).

outputFormat

Output a single integer to standard output (stdout) representing the maximum number of students that can be enrolled in a course under the given constraints.

4 4
1 0 1 0
0 1 1 1
1 1 1 0
0 1 1 1

4