There is a survey that consists of n questions where each question's answer is either 0 (no) or 1 (yes).

The survey was given to m students numbered from 0 to m - 1 and m mentors numbered from 0 to m - 1. The answers of the students are represented by a 2D integer array students where students[i] is an integer array that contains the answers of the ith student (0-indexed). The answers of the mentors are represented by a 2D integer array mentors where mentors[j] is an integer array that contains the answers of the jth mentor (0-indexed).

Each student will be assigned to one mentor, and each mentor will have one student assigned to them. The compatibility score of a student-mentor pair is the number of answers that are the same for both the student and the mentor.


	For example, if the student's answers were [1, 0, 1] and the mentor's answers were [0, 0, 1], then their compatibility score is 2 because only the second and the third answers are the same.


You are tasked with finding the optimal student-mentor pairings to maximize the sum of the compatibility scores.

Given students and mentors, return the maximum compatibility score sum that can be achieved.

&nbsp;
Example 1:

Input: students = [[1,1,0],[1,0,1],[0,0,1]], mentors = [[1,0,0],[0,0,1],[1,1,0]]
Output: 8
Explanation:&nbsp;We assign students to mentors in the following way:
- student 0 to mentor 2 with a compatibility score of 3.
- student 1 to mentor 0 with a compatibility score of 2.
- student 2 to mentor 1 with a compatibility score of 3.
The compatibility score sum is 3 + 2 + 3 = 8.


Example 2:

Input: students = [[0,0],[0,0],[0,0]], mentors = [[1,1],[1,1],[1,1]]
Output: 0
Explanation: The compatibility score of any student-mentor pair is 0.


&nbsp;
Constraints:


	m == students.length == mentors.length
	n == students[i].length == mentors[j].length
	1 &lt;= m, n &lt;= 8
	students[i][k] is either 0 or 1.
	mentors[j][k] is either 0 or 1.


import heapq
from collections import defaultdict

class Solution:
    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:
        m, n = len(students), len(students[0])
        def hamming(student, mentor):
            return sum([int(student[i] != mentor[i]) for i in range(n)])

        pq = [(0, 0, '0'*m)] # state: (n-comp_score aka Hamming distance, number of assigned students, mentor status)
        optimal = defaultdict(lambda:float('inf'))

        while pq: # O(V)
            cost, i, mentor_status = heapq.heappop(pq) # O(logV)

            # early stopping with termination condition
            if i == m:
                return m * n - cost

            # generate successors. The next student to be assigned is at index i
            for j, mentor in enumerate(mentors): # O(m)
                if mentor_status[j] != '1':
                    new_cost = cost + hamming(students[i], mentor)
                    new_mentor_status = mentor_status[:j] + '1' + mentor_status[j+1:]

                    # update optimal cost if a new successor appears with lower cost to the same node
                    if new_cost < optimal[(i+1, new_mentor_status)]:
                        optimal[(i+1, new_mentor_status)] = new_cost
                        heapq.heappush(pq, (new_cost, i+1, new_mentor_status)) # O(logV)

        return 0
class Solution {
    int max;
    public int maxCompatibilitySum(int[][] students, int[][] mentors) {
        boolean[] visited = new boolean[students.length];
        helper(visited, students, mentors, 0, 0);
        return max;
    }
    public void helper(boolean[] visited, int[][] students, int[][] mentors, int pos, int score){
        if(pos >= students.length){
            max = Math.max(max, score);
            return;
        }
        for(int i = 0; i < mentors.length; i++)
            if(!visited[i]){
                visited[i] = true;
                helper(visited, students, mentors, pos + 1, score + score(students[pos], mentors[i]));
                visited[i] = false;
            }
    }
    public int score(int[] a, int[] b){
        int count = 0;

        for(int i = 0; i < b.length; i++)
            if(a[i] == b[i]) count += 1;
        return count;
    }
}
class Solution {
    // Calculating compatibility scores of ith student and jth mentor
    int cal(int i,int j,vector<vector<int>>& arr1,vector<vector<int>>& arr2){
        int cnt=0;
        for(int k=0;k<arr1[0].size();k++){
            if(arr1[i][k]==arr2[j][k]){
                cnt++;
            }
        }
        return cnt;
    }

    int helper(int i,int m,vector<vector<int>>& arr1,vector<vector<int>>& arr2,vector<bool>& vis){
        if(i==m){
            return 0;
        }
        int ans = 0;
        for(int j=0;j<m;j++){
            if(!vis[j]){
                vis[j]=1;
                ans = max(ans,cal(i,j,arr1,arr2) + helper(i+1,m,arr1,arr2,vis));
                vis[j]=0; // Backtracking
            }
        }
        return ans;
    }

public:
    int maxCompatibilitySum(vector<vector<int>>& students, vector<vector<int>>& mentors) {
        int m = students.size();
        vector<bool> vis(m,0); // To keep track of which mentor is already paired up
        return helper(0,m,students,mentors,vis);
    }
};
var maxCompatibilitySum = function(students, mentors) {
    const m = students.length;
    const n = students[0].length;

    let max = 0;

    dfs(0, (1 << m) - 1, 0);

    return max;

    function dfs(studentIdx, bitmask, scoreTally) {
        if (studentIdx === m) {
            max = Math.max(max, scoreTally);

            return;
        }

        for (let mentorIdx = 0; mentorIdx < m; ++mentorIdx) {
            if (bitmask & (1 << mentorIdx)) {
                const matchScore = hammingDistance(students[studentIdx], mentors[mentorIdx]);
                const setMask = bitmask ^ (1 << mentorIdx);

                dfs(studentIdx + 1, setMask, scoreTally + matchScore);
            }
        }

        return;
    }

    function hammingDistance(studentsAnswers, mentorsAnswers) {
        let matches = 0;

        for (let j = 0; j < n; ++j) {
            if (studentsAnswers[j] === mentorsAnswers[j]) ++matches;
        }

        return matches;
    }
};
Maximum Compatibility Score Sum