Inverting Amplifier

The first line of input contains three space-separated integers: 'N', 'M', and 'K'.

The next 'N' lines each contain a string of 'M' characters ('0' or '1'), representing a row of the binary matrix.

Print a single integer representing the maximum number of rows that can be made entirely of '1's.

The key constraint is performing the operation exactly 'K' times.

Toggling the same column twice is equivalent to not toggling it at all. This means if a row needs c columns to be toggled to become all '1's, it can be achieved with K operations if and only if c <= K and (K - c) is an even number. The remaining K - c operations can be spent on toggling any column and then toggling it back.

The most efficient approach is to iterate through each row of the matrix, consider it as a "target pattern," and calculate the result if we were to make that specific pattern all '1's.

Sample Input 1:

2 3 3
000
010

Sample Output 1:

1

Explanation for Sample 1:

We have K=3 operations.
- To make the first row "000" into "111", we need to toggle all 3 columns. Cost = 3. `K=3`. Since `3 <= 3` and `(3-3)` is even, this is possible. If we do this, the first row becomes "111". The second row "010" becomes "101". We get 1 full row.
- To make the second row "010" into "111", we need to toggle the first and third columns. Cost = 2. `K=3`. `3-2=1` (odd parity). This is not possible with exactly 3 toggles.
The maximum we can achieve is 1 row.

Sample Input 2:

2 2 0
11
10

Sample Output 2:

1

Explanation for Sample 2:

We have K=0 operations (we can do nothing).
The first row is already "11". The second is "10".
The maximum number of all-'1' rows without any changes is 1.

Expected Time Complexity:

The expected time complexity is O(N * M).

Constraints:

1 <= N, M <= 100
0 <= K <= N * M

Time limit: 1 sec