Group Formation and Scheduling Problem

You are given a set of N students, M available group time slots, and a minimum required group size G. In addition, a compatibility matrix \(P\) of size \(N\times N\) is provided, where \(P[i][j]=1\) means that student \(i\) can work with student \(j\) (and \(0\) otherwise). There is also a schedule matrix \(S\) of size \(N\times M\) where \(S[i][k]=1\) indicates student \(i\) is available in time slot \(k\).

Your task is to form as many groups as possible while meeting the following conditions:

• For each group, all students must be available in the chosen time slot.
• Any two students in the same group must be pairwise compatible (i.e. for every two students \(i\) and \(j\) in the group, \(P[i][j]=1\)).
• Each group must contain at least \(G\) students.
• A student can be in at most one group.

This problem is challenging because it involves checking compatibility among subsets of students and scheduling constraints. Note that if a group meeting these requirements cannot be formed in a certain time slot, you may have to move on to the next time slot. Use a greedy strategy to attempt forming a valid group in each time slot. A useful hint is that one way to approximate the condition for the minimum group size is to check if there are enough valid candidate pairs among available students; for example, when \(G\) is even, you need at least \(\frac{G}{2}\) pairs. (When \(G\) is odd, we compare against \(\frac{G}{2}\) in floating point.)

Note: The method of grouping used in your solution should ensure that each formed group only uses students that have not been previously assigned, and once a group is formed, all those students cannot be reused for later groups.

inputFormat

The input is read from stdin and has the following format:

N M G
P[0][0] P[0][1] ... P[0][N-1]
P[1][0] P[1][1] ... P[1][N-1]
...
P[N-1][0] P[N-1][1] ... P[N-1][N-1]
S[0][0] S[0][1] ... S[0][M-1]
S[1][0] S[1][1] ... S[1][M-1]
...
S[N-1][0] S[N-1][1] ... S[N-1][M-1]

Where:

• N (1 ≤ N ≤ 200) is the number of students.
• M (1 ≤ M ≤ 50) is the number of group time slots available.
• G (1 ≤ G ≤ 5) is the minimum number of students required in each group.
• The next N lines describe the compatibility matrix \(P\). Each line has \(N\) integers (each 0 or 1).
• The following N lines describe the availability matrix \(S\). Each line has \(M\) integers (each 0 or 1).

outputFormat

Output a single integer on stdout — the maximum number of groups that can be formed under the given constraints.

## sample

5 3 2
1 1 0 1 1
1 1 1 1 0
0 1 1 0 0
1 1 0 1 1
1 0 0 1 1
1 1 0
0 1 1
1 0 1
0 1 1
1 1 0

2