1 /*************************************************************************
 2     > File Name: hdu-2255.奔小康赚大钱.cpp
 3     > Author: CruelKing
 4     > Mail: 2016586625@qq.com 
 5     > Created Time: 2019年09月04日 星期三 00时01分32秒
 6     本题思路:最大权完备匹配裸题
 7  ************************************************************************/
 8 
 9 #include <cstdio>
10 #include <cstring>
11 using namespace std;
12 
13 const int maxn = 300 + 5, inf = 0x3f3f3f3f;
14 int n, g[maxn][maxn];
15 int linker[maxn], lx[maxn], ly[maxn], slack[maxn];
16 bool visy[maxn], visx[maxn];
17 
18 bool dfs(int x) {
19     visx[x] = true;
20     for(int y = 1; y <= n; y ++) {
21         if(visy[y]) continue;
22         int temp = lx[x] + ly[y] - g[x][y];
23         if(temp == 0) {
24             visy[y] = true;
25             if(linker[y] == -1 || dfs(linker[y])) {
26                 linker[y] = x;
27                 return true;
28             }
29         }
30         else if(slack[y] > temp) slack[y] = temp;
31     }
32     return false;
33 }
34 
35 int km() {
36     memset(linker, -1, sizeof linker);
37     memset(ly, 0, sizeof ly);
38     for(int i = 1; i <= n; i ++) {
39         lx[i] = -inf;
40         for(int j = 1; j <= n; j ++) 
41             if(g[i][j] > lx[i])    lx[i] = g[i][j];
42     }
43     for(int x = 1; x <= n; x ++) {
44         for(int i = 1; i <= n; i ++)
45             slack[i] = inf;
46         while(true) {
47             memset(visx, false, sizeof visx);
48             memset(visy, false, sizeof visy);
49             if(dfs(x)) break;
50             int d = inf;
51             for(int i = 1; i <= n; i ++) 
52                 if(!visy[i] && d > slack[i]) d = slack[i];
53             for(int i = 1; i <= n; i ++)
54                 if(visx[i]) lx[i] -= d;
55             for(int i = 1; i <= n; i ++) {
56                 if(visy[i]) ly[i] += d;
57                 else slack[i] -= d;
58             }
59         }
60     }
61     int res = 0;
62     for(int i = 1; i <= n; i ++) 
63         if(linker[i] != -1) res += g[linker[i]][i];
64     return res;
65 }
66 
67 int main() {
68     while(~scanf("%d", &n)) {
69         for(int i = 1; i <= n; i ++) {
70             for(int j = 1; j <= n; j ++) {
71                 scanf("%d", &g[i][j]);
72             }
73         }
74         printf("%d\n", km());
75     }
76     return 0;
77 }