Maximum Saplings Planting

You are given a garden represented as a binary grid of size (R \times C). Each cell is either fertile (1) or infertile (0). You need to plant saplings in such a way that no two saplings share the same row or the same column. In other words, each sapling must be planted on a fertile cell and no row or column can contain more than one sapling.

This problem can be modeled as a maximum bipartite matching problem. Consider the rows as one set and the columns as another set. An edge exists between row (i) and column (j) if and only if the cell ((i,j)) is fertile (i.e. has a value of 1). The maximum number of saplings you can plant is equivalent to the size of the maximum matching in this bipartite graph.

A standard approach to solve this is using DFS based matching algorithms. The matching algorithm finds an assignment such that each selected cell is unique in its row and column.

For example, given the garden grid:

[ \begin{matrix} 1 & 0 & 0 & 1 \ 0 & 1 & 0 & 0 \ 0 & 0 & 1 & 0 \end{matrix} ]

One valid solution is to plant saplings in cells ((0,0)), ((1,1)), and ((2,2)), making the maximum number of saplings 3.

inputFormat

The input consists of multiple lines. The first line contains two integers, (R) and (C), denoting the number of rows and columns of the garden. Each of the next (R) lines contains (C) integers (either 0 or 1) separated by spaces, representing the garden grid.

outputFormat

Output a single integer — the maximum number of saplings that can be planted such that no two saplings share the same row or the same column.## sample

3 4
1 0 0 1
0 1 0 0
0 0 1 0

3