#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

constexpr int inf = 1000000001;

auto cmp = [](const pair<int, int>& a, const pair<int, int>& b){
	return a.first > b.first; };

void dijkstra(const int surs, const int dest,
	const vector<vector<int> >& graf,
	const vector<vector<int> >& cap, const vector<vector<int> >& flux, const vector<vector<int> >& lung,
	vector<int>& dist, vector<int>& tata){

	fill(begin(dist), end(dist), inf), fill(begin(tata), end(tata), -1);
	static priority_queue<pair<int, int>, vector<pair<int, int> >, decltype(cmp)> de_viz(cmp);
	while(!de_viz.empty()){
		de_viz.pop(); }

	dist[surs] = 0;
	tata[surs] = surs;
	de_viz.emplace(0, surs);

	while(!de_viz.empty()){
		const int cur = de_viz.top().second, dist_cur = de_viz.top().first;
		de_viz.pop();
		if(cur == dest){
			return; }
		if(dist_cur != dist[cur]){
			continue; }

		for(const auto next : graf[cur]){
			if(cap[cur][next] - flux[cur][next] > 0 && dist_cur + lung[cur][next] < dist[next]){
				dist[next] = dist_cur + lung[cur][next];
				tata[next] = cur;
				de_viz.emplace(dist[next], next); } } } }

int fmcm(const int surs, const int dest,
	const vector<vector<int> >& graf, const vector<vector<int> >& cap,
	vector<vector<int> >& flux, const vector<vector<int> >& lung){

	const int n = graf.size();

	vector<int> dist(n), tata(n);
	int rez = 0;

	while(true){
		dijkstra(surs, dest, graf, cap, flux, lung, dist, tata);
		if(tata[dest] == -1){
			return rez; }
		int flux_aug = inf;
		for(int cur = dest; cur != surs; cur = tata[cur]){
			flux_aug = min(flux_aug, cap[tata[cur]][cur] - flux[tata[cur]][cur]);
			rez += lung[tata[cur]][cur]; }
		for(int cur = dest; cur != surs; cur = tata[cur]){
			flux[tata[cur]][cur] += flux_aug;
			flux[cur][tata[cur]] -= flux_aug; } } }

void add_lat(const int a, const int b, const int c, vector<vector<int> >& graf, vector<vector<int> >& cap, vector<vector<int> >& flux, vector<vector<int> >& lung){
	graf[a].push_back(b);
	graf[b].push_back(a);
	cap[a][b] = 1;
	lung[a][b] = c;
	lung[b][a] = -c; }

void read_graf(int& surs, int& dest, vector<vector<int> >& graf, vector<vector<int> >& cap, vector<vector<int> >& flux, vector<vector<int> >& lung){
	ifstream f("cc.in");
	int n;
	f >> n;
	surs = 0;
	const int st_oameni = 1, st_computere = n+1;
	dest = 2*n+1;
	graf.resize(dest+1);
	cap.resize(dest+1, vector<int>(dest+1, 0)), flux.resize(dest+1, vector<int>(dest+1, 0)),
		lung.resize(dest+1, vector<int>(dest+1, 0));
	for(int i = 0; i < n; ++i){
		add_lat(surs, st_oameni + i, 0, graf, cap, flux, lung); }
	for(int i = 0; i < n; ++i){
		add_lat(st_computere + i, dest, 0, graf, cap, flux, lung); }
	for(int i = 0, x; i < n; ++i){
		for(int j = 0; j < n; ++j){
			f >> x;
			add_lat(st_oameni + i, st_computere + j, x, graf, cap, flux, lung); } } }

int main(){
	int surs, dest;
	vector<vector<int> > graf, cap, flux, lung;
	read_graf(surs, dest, graf, cap, flux, lung);
	ofstream g("cc.out");
	for(const auto y : lung){
		for(const auto x : y){
			cout << x << ' '; }
		cout << endl; }
	g << fmcm(surs, dest, graf, cap, flux, lung);
	return 0; }