/*ID:esxgx1LANG:C++PROG:hdu2255*/#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;typedef long long LL;#define LXN        307#define RXN        307int w[LXN][RXN];int lx[LXN], ly[RXN];char visx[LXN], visy[RXN];int matched[RXN], slack[RXN];int N;#define LN        N#define RN        Nint aug(int i){    visx[i] = 1;    for(int j=0; j<RN; ++j) {        if (!visy[j]) {            int d = lx[i] + ly[j] - w[i][j];            if (!d) {                visy[j] = 1;                if (matched[j] < 0 || aug(matched[j])) {                    matched[j] = i;                    return 1;                }            } else if (slack[j] > d) slack[j] = d;        }    }    return 0;}#define INF        0x3f3f3f3fvoid work(void){    for(int i=0; i<LN; ++i) {        lx[i] = w[i][0];        for(int j = 1; j<RN; ++j)            if (w[i][j] > lx[i]) lx[i] = w[i][j];    }    for(int i=0; i<RN; ++i) ly[i] = 0;    memset(matched, -1, sizeof(matched));    // Kuhn-Munkres    for(int i=0; i<LN; ++i) {        for (int j=0; j<RN; ++j)            slack[j] = INF;        while(1) {            memset(visx, 0, sizeof(visx));            memset(visy, 0, sizeof(visy));            if (aug(i)) break;            int d, j = 0;            for(; j<RN; ++j) if (!visy[j]) {d = j; break;}            for(; j<RN; ++j)                if (!visy[j] && slack[d] > slack[j])                    d = j;            d = slack[d];            for(int j=0; j<LN; ++j)    if (visx[j]) lx[j] -= d;            for(int j=0; j<RN; ++j)                if (visy[j]) ly[j] += d;                else slack[j] -= d;        }    }}// x (- [a, b] 优化#define within(x, a, b)        ((unsigned)((x) - (a)) <= ((b) - (a)))// 读入一个整数[返回值同scanf]int readint(int *p){    int ch;    while(!within(ch=getchar(), ‘0‘, ‘9‘))        if(ch == EOF) return EOF;    int rslt = 0;    do        rslt = rslt * 10 + (ch - ‘0‘);    while(within(ch=getchar(), ‘0‘, ‘9‘));    *p = rslt;    return 1;}int println_int(int i){    char s[107], p = 0;    while(i) {        s[p++] = i % 10;        i/=10;    }    while(p) putchar(‘0‘ + s[--p]);    putchar(‘\n‘);}int main(void){    #ifndef ONLINE_JUDGE    freopen("in.txt", "r", stdin);    #endif    while(readint(&N) > 0) {        for(int i=0; i<N; ++i)            // 第i个村子            for(int j=0; j<N; ++j)                 readint(&w[i][j]);        work();        int z = 0;        for(int j=0; j<RN; ++j)            if (matched[j] >= 0) z += w[matched[j]][j];        println_int(z);    }    return 0;}