1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 #define mem(x,y) memset(x,y,sizeof(x))
 7 const int MAXN=310;
 8 const int INF=0x3f3f3f3f;
 9 int mat[MAXN],mp[MAXN][MAXN],lx[MAXN],ly[MAXN];
10 int usdx[MAXN],usdy[MAXN];
11 int n;
12 bool dfs(int x){
13     usdx[x]=1;
14     for(int i=1;i<=n;i++){
15         if(!usdy[i]&&lx[x]+ly[i]==mp[x][i]){//注意这里是x 
16             usdy[i]=1;
17             if(!mat[i]||dfs(mat[i])){
18                 mat[i]=x;return true;
19             }
20         }
21     }
22     return false;
23 }
24 int km(){
25     mem(mat,0);mem(lx,0);mem(ly,0);
26     for(int i=1;i<=n;i++)
27     for(int j=1;j<=n;j++)
28     lx[i]=max(lx[i],mp[i][j]);
29     for(int i=1;i<=n;i++){
30         mem(usdx,0);mem(usdy,0);
31         while(!dfs(i)){
32             int d=INF;
33             for(int j=1;j<=n;j++)
34             if(usdx[j])
35             for(int k=1;k<=n;k++)
36                 if(!usdy[k])
37                 d=min(d,lx[j]+ly[k]-mp[j][k]);//注意这里是k 
38             for(int j=1;j<=n;j++){
39                 if(usdx[j])lx[j]-=d;
40                 if(usdy[j])ly[j]+=d;
41             }
42             mem(usdx,0);mem(usdy,0);
43         }
44     }
45     int ans=0;
46     for(int i=1;i<=n;i++)ans+=lx[i]+ly[i];
47     return ans;
48 }
49 int main(){
50     while(~scanf("%d",&n)){
51         mem(mp,0);
52         for(int i=1;i<=n;i++)
53             for(int j=1;j<=n;j++)
54                 scanf("%d",&mp[i][j]);
55         printf("%d\n",km());
56     }
57     return 0;
58 }