#include "iostream"
#include <fstream>

using namespace std;

int mat[20][20], n, col[20], lin[20], zero[20], l[20], c[20];

int minim()
{
	int minim = 999;
	for (int i = 1; i <= n; i++)
	for (int j = 1; j <= n; j++)
	if (!l[i] && !c[j] && minim > mat[i][j] - (lin[i] + col[j]))
		minim = mat[i][j] - (lin[i] + col[j]);
	return minim;
}

bool ver_coloana(int i)
{
	for (int k = 1; k <= n; k++)
		if (zero[k] == i)
			return false;
	return true;
}

int verificare(int i, int j)
{
	int counter = 0, var;
	if (i)
	{
		for (int j = 1; j <= n; j++)
		if (mat[i][j] - (lin[i] + col[j]) == 0 && ver_coloana(j) && !zero[i])
		{
			counter++;
			var = j;
		}

		if (counter == 1)
			return var;
		else
			return 0;
	}
	else
	{
		for (int i = 1; i <= n; i++)
		if (mat[i][j] - (lin[i] + col[j]) == 0 && !zero[i] && ver_coloana(j))
		{
			counter++;
			var = i;
		}
		if (counter == 1)
			return var;
		else
			return 0;
	}
	
}

void bozgor()
{
	int min, counter = 0;
	for (int i = 1; i <= n; i++)
	{
		min = 999;
		for (int j = 1; j <= n; j++)
		if (mat[i][j] < min)
		{
			min = mat[i][j];
			lin[i] = min;
		}
	}
	for (int i = 1; i <= n; i++)
	{
		min = 999;
		for (int j = 1; j <= n; j++)
		if (mat[j][i] - lin[j] < min)
		{
			min = mat[j][i] - lin[j];
			col[i] = min;
		}
	}
	while (counter != n)
	{
		for (int i = 1; i <= n; i++)
			zero[i] = 0;
		counter = 0;
		bool gasit = true;
		
		while (gasit)
		{
			gasit = false;
			for (int i = 1; i <= n; i++)
			{
				int temp = 0;
				temp = verificare(i, 0);
				if (temp)
				{
					zero[i] = temp;
					gasit = true;
				}
			}
			for (int i = 1; i <= n; i++)
			{
				int temp = 0;
				temp = verificare(0, i);
				if (temp)
				{
					zero[temp] = i;
					gasit = true;
				}
			}

		}

		for (int i = 1; i <= n; i++)
		if (zero[i])
			counter++;
		if (counter != n)
		{
			for (int i = 1; i <= n; i++)
			{
				if (zero[i] == 0)
					l[i] = 0;
				else
					l[i] = 1;
				c[i] = 0;
			}
			gasit = true;
			while (gasit)
			{
				gasit = false;
				for (int i = 1; i <= n; i++)
				if (l[i] == 0)
				{
					for (int j = 1; j <= n; j++)
					if (mat[i][j] - (lin[i] + col[j]) == 0 && zero[i] != j && c[j] == 0)
					{
						c[j] = 1;
						gasit = true;
					}

				}
				for (int j = 1; j <= n; j++)
				if (c[j] == 1)
				{
					for (int i = 1; i <= n; i++)
					if (zero[i] == j && l[i] == 1)
					{
						gasit = true;
						l[i] = 0;
					}

				}

			}
			int rez = minim();
			for (int i = 1; i <= n; i++)
			{
				if (l[i] == 0)
					lin[i] += rez;
				if (c[i] == 1)
					col[i] -= rez;
			}

		}
	}
}

int main()
{
	int suma = 0;
	ifstream file;
	file.open("cc.in");
	file >> n;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			file >> mat[i][j];
	file.close();

	bozgor();


	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
			cout << mat[i][j] << " ";
		cout << endl;
	}
	
	for (int i = 1; i <= n; i++)
		suma += mat[i][zero[i]];

	cout <<endl<< "Suma minima este : "<<suma<<endl;
	for (int i = 1; i <= n; i++)
		cout << "Perechile sunt : " << i << " -> " << zero[i] << endl;
	cin.get();
	ofstream x("cc.out");
	x<<suma;
	return 0;
}