#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cassert>
#include <set>

using namespace std;

#define all(c)    (c).begin(),  (c).end()
#define rall(c)  (c).rbegin(), (c).rend()

#define _auto(var, x)           typeof(x) var = (x)
#define _auxforeach(it, b, e)   for(_auto(it, b), _itend = e; it != _itend; ++it)
#define foreach(it, r...)       _auxforeach(it, r)

typedef long long LLONG;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;

enum { INF = 1<<30 };

struct HungaroMatching{
	vector<vector<int> > cost;
	int n;
	int max_match;
	vector<int> lx, ly;
	vector<int> xy, yx;
	vector<bool> R, T;
	vector<int> excess, whomatch, prev;

	void init_labels(){
		foreach(it, all(lx)) *it=0;
		foreach(it, all(ly)) *it=0;
		for (int x = 0; x < n; x++)
			for (int y = 0; y < n; y++)
				lx[x] = max(lx[x], cost[x][y]);
	}

	void update_labels(){
		int x, y;
		int e = INF;
		for (y = 0; y < n; y++)	if (!T[y]) e = min(e, excess[y]);
		for (x = 0; x < n; x++)	if (R[x]) lx[x] -= e;
		for (y = 0; y < n; y++) if (T[y]) ly[y] += e;
		for (y = 0; y < n; y++) if (!T[y]) excess[y] -= e;
	}

	void add(int x, int prevx){
		R[x] = true;
		prev[x] = prevx;
		for (int y = 0; y < n; y++)
			if (lx[x] + ly[y] - cost[x][y] < excess[y]){
				excess[y] = lx[x] + ly[y] - cost[x][y];
				whomatch[y] = x;
			}
	}

	void augment()
	{
	    int x, y, root;
	    do{
            if (max_match == n) return;
            vector<int> q(n); //used as a queue
            int qend = 0, qbeg = 0; //
            R = vector<bool>(n, false);
            T = vector<bool>(n, false);

            foreach(it, all(prev)) *it = -1;
            // prev store the nodes to build a matching its a tree

            // start to build a new augmented matching
            for (x = 0; x < n; x++)
                if (xy[x] == -1){
                    root = x;
                    q[qend++] = root;
                    prev[x] = -2;
                    R[x] = true;
                    break;
                }

            // store witch is the excess
            for (y = 0; y < n; y++){
                excess[y] = lx[root] + ly[y] - cost[root][y];
                whomatch[y] = root;
            }

            while (true){
                while (qbeg < qend){
                    x = q[qbeg++];
                    for (y = 0; y < n; y++)
                        if (cost[x][y] == lx[x] + ly[y] &&  !T[y]){
                            if (yx[y] == -1) break;
                            T[y] = true;
                            q[qend++] = yx[y];
                            add(yx[y], x);
                        }
                    if (y < n) break;
                }
                if (y < n) break;

                update_labels();

                // its possible augment?
                qend = qbeg = 0;
                for (y = 0; y < n; y++)
                    if (!T[y] &&  excess[y] == 0){
                        if (yx[y] == -1){
                            x = whomatch[y];
                            break;
                        }
                        else{
                            T[y] = true;
                            if (!R[yx[y]]){
                                q[qend++] = yx[y];
                                add(yx[y], whomatch[y]);
                            }
                        }
                    }
                if (y < n) break;
            }

            if (y < n){
                max_match++;
                //mounting the new matching
                for (int cx = x, cy = y, ty; cx != -2; cx = prev[cx], cy = ty){
                    ty = xy[cx];
                    yx[cy] = cx;
                    xy[cx] = cy;
                }
            }
            //if is possible augment
        }while(y < n);
	}

	int getMaxCost(){
		int ret = 0;                //weight of the optimal matching
		max_match = 0;
		foreach(it, all(xy)) *it=-1;
		foreach(it, all(yx)) *it=-1;                    //number of vertices in current matching
		init_labels();                    //step 0
		augment();                        //steps 1-3
		for (int x = 0; x < n; x++){      //forming answer there
			ret += cost[x][xy[x]];
		}
		return ret;
	}
	HungaroMatching(int n, vector<vector<int> > cost): n(n), cost(cost){
        lx = vector<int>(n);
        ly = vector<int>(n);
        xy = vector<int>(n);
        yx = vector<int>(n);
        excess = vector<int>(n);
        whomatch = vector<int>(n);
        prev = vector<int>(n);
        R = vector<bool>(n);
        T = vector<bool>(n);
    }
};

int main() {
    int n, f;
    char operation[5];
    gets(operation);
    f = -strcasecmp(operation, "MC");

    scanf("%d", &n);
    VVI cost(n, VI(n));
    for(int i=0; i<n; ++i){
        for(int j=0; j<n; ++j){
            scanf("%d", &cost[i][j]);
            cost[i][j] *=f;
        }
    }
    HungaroMatching res(n, cost);
    printf("\nRESULTADO = %d\n\n", abs(res.getMaxCost()));
    puts("MATCHING:");
    for(int x=0; x<n; ++x){
        printf("%d -> %d\n", x+1, res.xy[x]+1);
    }
    return 0;
}