/**
 * Sergey Kopeliovich (burunduk30@gmail.com)
 */

#include <bits/stdc++.h>
#include "optimization.h"

using namespace std;

#define forn(i, n) for (int i = 0; i < (int)(n); i++)

const int N = 303;
const int alpha = 3;

int a[N][N];
int width, height, matrix[N][N], row[N];

void solve() {
	iota(row, row + width, 0);
	vector<int> price(width, 0);
	int eps = 0;
	forn(i, height) {
		forn(j, width) {
			matrix[i][j] *= 1 + max(width, height);
			eps = max(eps, matrix[i][j]);
		}
	}
	while (eps > 1) {
		eps = (eps + alpha - 1) / alpha;
		fill(row, row + width, -1);
		forn(v, height) {
			for (int source = v; source != -1; ) {
				int best = -1, cost, mi1 = INT_MAX, mi2 = INT_MAX;
				forn(i, width)
					if ((cost = matrix[source][i] - price[i]) < mi1)
						best = i, mi2 = mi1, mi1 = cost;
					else if (cost < mi2)
						mi2 = cost;
				swap(row[best], source);
				price[best] -= (mi2 - mi1) + eps;
			} 
		}
	}
}

int main() {
	int n = readInt();
	width = height = n;
	forn(i, n)
		forn(j, n)
			a[i][j] = matrix[i][j] = readInt();

	solve();

	int sum = 0;
	forn(i, n)
		sum += a[row[i]][i];
	printf("%d\n", sum);
	forn(i, n)
		printf("%d %d\n", row[i] + 1, i + 1);
};