// Arup Guha
// 2/3/2010
// Solution to COP 3502 Program #2: Match Making

#include <stdio.h>
#include <math.h>

#define MAX 10
#define NAME_MAX 20

void nextPerm(int perm[], int length);
int fact(int n);
int getMatchScore(int perm[], int mens_ratings[][MAX], int womens_ratings[][MAX], int length);
int getMatchDiff(int perm[], int mens_ratings[][MAX], int womens_ratings[][MAX], int length);
void copy(int a[],int b[], int size);
void output(char men[][NAME_MAX], char women[][NAME_MAX], int perm[], int length);

int main() {
    
    FILE* ifp = fopen("matching.txt","r");

    int loop, numcases;
    fscanf(ifp, "%d", &numcases);
    
    // Go through each case.
    for (loop=1; loop <=numcases; loop++) {

        // Get the number of couples.    
        int size;
        fscanf(ifp, "%d", &size);

        // Initialize the permutation matrix for the females.
        int fem_perm[MAX], best_perm[MAX];
        int i,j;
        for (i=0; i<size; i++) {
            fem_perm[i] = i;
            best_perm[i] = i;
        }
        
        // Read in everyone's names.
        char men[MAX][NAME_MAX], women[MAX][NAME_MAX];
        for (i=0; i<size; i++)
            fscanf(ifp, "%s", men[i]);
        for (i=0; i<size; i++)
            fscanf(ifp, "%s", women[i]);
            
        // Read in everyone's ratings.
        int men_ratings[MAX][MAX], women_ratings[MAX][MAX];
        for (i=0; i<size; i++)
            for (j=0; j<size; j++)
                fscanf(ifp, "%d", &men_ratings[i][j]);
        for (i=0; i<size; i++)
            for (j=0; j<size; j++)
                fscanf(ifp, "%d", &women_ratings[i][j]);
                
        int best_score=0, best_diff=0;
                
        // Go through the correct number of permutations
        for (i=0; i<fact(size); i++) {
            
            // Just calculate both of these. It might be somewhat inefficient, but
            // this makes the code a bit easier.
            int this_score = getMatchScore(fem_perm, men_ratings, women_ratings, size);
            int this_diff =  getMatchDiff(fem_perm, men_ratings, women_ratings, size);
            
            // We have a new best matching, update!
            if (this_score > best_score || (this_score == best_score && this_diff < best_diff)) {
                copy(best_perm, fem_perm, size);
                best_score = this_score;
                best_diff = this_diff;
            }
    
            // Advance to the next permutation.        
            nextPerm(fem_perm, size);
        }
        
        // Output answers.
        printf("Matching #%d: Maximum Score = %d.\n\n", loop, best_score);
        output(men, women, best_perm, size);
        printf("\n\n");
        
    }
    
    fclose(ifp);
    //system("PAUSE");
    return 0;
}

// Returns n!, works for 0 <= n <= 12.
int fact(int n) {
    if (n == 0)
        return 1;
    else
        return n*fact(n-1);
}

// Changes perm to be the next lexicographical permutation. If none exists,
// then perm remains unchanged. (This only occurs when perm is in 
// descending order.
void nextPerm(int perm[], int length) {
		
    // Find the spot that needs to change.
    int i = length-1;
    while (i>0 && perm[i] < perm[i-1]) i--;
    i--; // Advance to the location that needs to be swapped.
		
    // So last perm doesn't cause a problem.
    if (i == -1) return;
		
    // Find the spot with which to swap index i.
    int j=length-1;
    while (j>i && perm[j]<perm[i]) j--;
		
    // Swap it.
    int temp = perm[i];
    perm[i] = perm[j];
    perm[j] = temp;
		
   // reverse from index i+1 to length-1.
   int k,m;
   for (k=i+1,m=length-1; k<m; k++,m--) {
       temp = perm[k];
       perm[k] = perm[m];
       perm[m] = temp;
    }
}

// Returns the score of matching the men with the women permuted in the order specified by
// perm. length specifies the number of men.
int getMatchScore(int perm[], int men_ratings[][MAX], int women_ratings[][MAX], int length) {

    int i, score = 0;
    
    // Go through each couple.
    for (i=0; i<length; i++) {
        
        // Guy was more stingy here.
        if (men_ratings[i][perm[i]] <= women_ratings[perm[i]][i])
            score += men_ratings[i][perm[i]];
        
        // Woman was more stingy here.
        else
            score += women_ratings[perm[i]][i];
    }
    return score;
}

// Returns the difference score of matching the men with the women permuted in 
// the order specified by perm. length specifies the number of men.
int getMatchDiff(int perm[], int men_ratings[][MAX], int women_ratings[][MAX], int length) {
    
    // Go through each couple and just add in the difference of scores.
    int i, score = 0;
    for (i=0; i<length; i++) 
        score += abs(men_ratings[i][perm[i]]-women_ratings[perm[i]][i]);
    
    return score;
}

// Copies the contents of the first size elements of b into the corresponding
// indexes in a.
void copy(int a[],int b[], int size) {
    int i;
    for (i=0; i<size; i++)
        a[i] = b[i];
}

// Outputs the men and women couple, with the men in their original ordering
// and the women in the ordering specified by perm, as couples.
void output(char men[][NAME_MAX], char women[][NAME_MAX], int perm[], int length) {

    int i;
    int s = 0;
    for (i=0; i<length; i++) 
        printf("%s %s\n", men[i], women[perm[i]]);   
}