#include <cstdio>
#include <cstring>
using namespace std;
const int nmax=150;

int a[ nmax ][ nmax ],mat[ nmax ][ nmax ],s[ nmax ][ nmax ],n;
int star_row[ nmax ],star_col[ nmax ],cov_row[ nmax ],cov_col[ nmax ];


void read() {
	FILE *fin = fopen ("cc.in","r");
	fscanf (fin,"%d",&n);
	int i,j,s[ nmax ];
	for (i=0; i<n; s[ i++ ]=0);
	for (i=0; i<n; ++i)
		for (j=0; j<n; ++j) {
			fscanf (fin,"%d",&a[ i ][ j ]);
			s[ j ]+=a[ i ][ j ];
		}
	for (i=0; i<n; ++i)
		for (j=0; j < n; ++j) {
/*			a[ i ][ j ]=s[j]-a[i][j];*/
			mat[ i ][ j ]=a[ i ][ j ];
// 			printf ("%d ",a[ i ][ j ]);
		}
}

int munkres() {
	int i,j,step=1;
	for (i=0; i<n; ++i) {
		int min=mat[ i ][ 0 ];
		for (j=1; j<n; ++j)
			if (mat[ i ][ j ] < min) min=mat[ i ][ j ];
		for (j=0; j<n; ++j) {
			mat[ i ][ j ]-=min;
			if (mat[ i ][ j ] == 0 && !star_col[ j ] && !star_row[i]) {
				star_col[ j ]=1;
				star_row[ i ]=1;
				s[ i ][ j ]=1; //* = 1, ' = 2
//  				printf ("Stea %d %d, min=%d\n",i,j,min);
			}
		}
	}
	
	while (1) {
		if (step == 1) {
//   			printf ("Step 1 ");
			int count=0;
			for (i=0; i<n; ++i) 
				if (star_col[ i ]) {
					cov_col[ i ]=1;
					count++;
				}
			
				
//  			printf ("Count=%d\n",count);
			if (count == n) break; //Avem solutie
		}
		
		int found,r,c;
		do {
//  			printf ("Ste 4\n");
			int k;
			found=0;
			for (i=0; i<n && !found; ++i)
				for (j=0; j<n && !found; ++j) 
					if (mat[ i ][ j ]==0 && !cov_row[ i ] && !cov_col[ j ]) found=1;
			--i;--j;
			if (found==0) break;
//  			printf ("Uncovered 0 at (%d,%d) ",i,j);
			s[ i ][ j ]=2;
			if (!star_row[ i ]) {
//  				printf ("Alone\n");
				found=3;
				r=i;
				c=j;
			}
			else {
				for (k=0; k < n; ++k) 
					if (s[ i ][ k ]==1) break;
				cov_row[ i ]=1;
				cov_col[ k ]=0;
//  				printf ("uncover (%d,%d)\n",i,k);
			}
		}while (found==1);
		if (found==3) { //Step 5
//  			printf ("Step 5 %d\n",s[ 0 ][ 1 ]);
			int k=0;
			star_row[ r ]=1;
			for (k=0; 1; ++k) {
//  				printf ("%d %d\n",r,c);
				if (k % 2==0) {
					int yy=r,xx=c;
					for (r=0; r < n; ++r)
						if (s[ r ][ c ]==1) {
							s[ r ][ c ]=0;
							break;
						}
					s[ yy ][ xx ]=1;
					if (r == n) 
						break;
				}
				else {
					for (c=0; c < n; ++c) 
						if (s[ r ][ c ]==2) {
							s[ r ][ c ]=0;
							break;
						}
				}
			}
			star_col[ c ]=1;
			for (i=0; i<n; ++i) {
				for (j=0; j<n; ++j) 
					if (s[ i ][ j ]==2) s[ i ][ j ]=0;
				cov_row[ i ]=0;
			}
			step=1;
		}
		else { //Step 6
//  			printf ("Step 6\n");
			int min=151;
//  			for (i=0; i<n; ++i)
//  				printf ("Cov row,col = %d, %d\n",cov_row[ i ],cov_col[ i ]);
			for (i=0; i<n; ++i)
				for (j=0; j<n; ++j)
					if (!cov_row[ i ] && !cov_col[ j ] && mat[ i ][ j ] < min) 
						min=mat[ i ][ j ];
//  			printf ("Min=%d\n",min);
			for (i=0; i<n; ++i)
				for (j=0; j<n; ++j) {
					if (cov_row[ i ]) mat[ i ][ j ]+=min;
					if (!cov_col[ j ]) mat[ i ][ j ]-=min;
				}
// 			for (i=0; i<n; ++i,printf ("\n") )
// 				for (j=0; j<n; ++j)
// 					printf ("%d ",mat[ i ][ j ]);
			step=2;
// 			int xxx;
// 			scanf ("%d",&xxx);
		}
	}
	int ret=0;
	for (i=0; i<n; ++i)
		for (j=0; j<n; ++j)
			if (s[ i ][ j ]==1) {
//  				printf ("%d %d\n",i,j);
				ret+=a[ i ][ j ];
			}
	return ret;
}

int main() {
	read();
// 	printf ("S-a citit\n");
	fprintf (fopen("cc.out", "w"), "%d",munkres() );
	return 0;
}