#include<cstdio>
#include<cstring>
using namespace std;
int min(int x,int y){return x<y?x:y;}
const int N=5e3+1;
struct edge{int next,to,w,cost;}d[N];
int head[N],cnt=1;
void add(int x,int y,int w,int c){
	d[++cnt]=(edge){head[x],y,w, c};head[x]=cnt;
	d[++cnt]=(edge){head[y],x,0,-c};head[y]=cnt;
}
int n,a[N][N],p[N],q[N],pre[N],dis[N],flow[N];
int bfs_max(){
	int l=0,r=1;
	memset(q,0,sizeof 0);
	memset(p,0,sizeof 0);
	memset(pre,0,sizeof 0);
	for(int i=0;i<N;i=-~i) dis[i]=-0x3f3f3f3f;
	memset(flow,0x3f,sizeof flow);
	p[0]=1,q[1]=dis[0]=0;
	while(l<r){
		int x=q[++l];
		p[x]=0;
		if(x==2*n+1) return 1;
		for(int i=head[x];i;i=d[i].next){
			int v=d[i].to,w=d[i].w,c=d[i].cost;
			if(w>0&&dis[x]+c>=dis[v]){
				pre[v]=i;
				if(!p[v]){p[v]=1;q[++r]=v;}
				dis[v]=dis[x]+c;
				flow[v]=min(flow[x],w);
			}
		}
	}
	return 0;
}
int bfs_min(){
	int l=0,r=1;
	memset(q,0,sizeof 0);
	memset(p,0,sizeof 0);
	memset(pre,0,sizeof 0);
	memset(dis,0x3f,sizeof dis);
	memset(flow,0x3f,sizeof flow);
	p[0]=1,q[1]=dis[0]=0;
	while(l<r){
		int x=q[++l];
		p[x]=0;
		if(x==2*n+1) return 1;
		for(int i=head[x];i;i=d[i].next){
			int v=d[i].to,w=d[i].w,c=d[i].cost;
			if(w>0&&dis[x]+c<=dis[v]){
				pre[v]=i;
				if(!p[v]){p[v]=1;q[++r]=v;}
				dis[v]=dis[x]+c;
				flow[v]=min(flow[x],w);
			}
		}
	}
	return 0;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i=-~i){
		for(int j=1;j<=n;j=-~j){
			scanf("%d",&a[i][j]);
			add(i,j+n,1,a[i][j]);
		}
		add(0,i,1,0),add(i+n,2*n+1,1,0);
	}
	int s=0,t=2*n+1,ans=0;
	while(bfs_min()){
		ans+=dis[t]*flow[t];
        int now=t;
        while(now!=s){
            d[pre[now]].w-=flow[t];
            d[pre[now]^1].w+=flow[t];
            now=d[pre[now]^1].to;
        }
	}
	printf("%d\n",ans);
    for(int i=2;i<=cnt;i+=2){
		d[i].w+=d[i^1].w;
		d[i^1].w=0;
	} 
    ans=0;
    while(bfs_max()){
        ans+=dis[t]*flow[t];
        int now=t;
        while(now!=s){
            d[pre[now]].w-=flow[t];
            d[pre[now]^1].w+=flow[t];
            now=d[pre[now]^1].to;
        }
    }
    printf("%d\n",ans);
	return 0;
}