#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;
}