/**
 * Author: Sergey Kopeliovich (Burunduk30@gmail.com)
 */

#include <cmath>
#include <cstdio>
#include <cstring>
#include <cassert>

#include <algorithm>
#include <vector>

using namespace std;

#define forn(i, n) for (int i = 0; i < (int)(n); i++)
#define pb push_back
#define sz(a) (int)(a).size()

typedef double dbl;
typedef vector <int> vi;

#define NAME "assignment2"

const int maxK = 100;
const int maxM = maxK * 2;
const int maxN = maxK * maxK + 1;
const dbl eps = 1e-9;

int n, m, K, matrix[maxK][maxK];
dbl a[maxM][maxN], c[maxN], x[maxN], lower[maxN], upper[maxN], df[maxN];
int w[maxN], p[maxN], u[maxN];
int cnt1 = 0;

inline void ChangeA( int i, int j, dbl val )
{
  df[j] -= (val - a[i][j]) * c[p[i]], a[i][j] = val;
}

void Do( int i, int j )
{
  int wn = 0;
  dbl x = 1.0 / a[i][j];
  forn(k, n + 1)
    if (fabs(a[i][k]) > eps)
      w[wn++] = k, ChangeA(i, k, a[i][k] * x);
  forn(y, m) if (y != i && fabs(x = a[y][j]) > eps)
    forn(k, wn)
      ChangeA(y, w[k], a[y][w[k]] - x * a[i][w[k]]);
  cnt1++;
}

void Change( int j, int dir, dbl val )
{
  int ri = -1;
  dbl ma = val;
  forn(i, m)
    if (fabs(a[i][j]) > eps)
    {
      dbl t, koef = 1.0 / (a[i][j] * dir);
      t = koef * (koef > 0 ? x[p[i]] - lower[p[i]] : x[p[i]] - upper[p[i]]);
      if (t < ma) ma = t, ri = i;
    }

  dbl dx = ma * dir;
  x[j] += dx;
  forn(i, m)
    if (fabs(a[i][j]) > eps)
      x[p[i]] -= (a[i][j] * dx) / a[i][p[i]];
  if (ri != -1)
  {
    forn(t, n)
      df[t] -= a[ri][t] * (c[j] - c[p[ri]]);
    u[p[ri]] = 0, u[p[ri] = j] = 1, Do(ri, j);
  }
}

int main()
{
  assert(freopen(NAME ".in", "r", stdin));
  assert(freopen(NAME ".out", "w", stdout));

  scanf("%d", &K);
  assert(K <= maxK);
  forn(i, K)
    forn(j, K)
      scanf("%d", &matrix[i][j]);

  m = 2 * K, n = K * K;
  forn(i, n)
    lower[i] = 0, upper[i] = 1, x[i] = 0;
  forn(i, K)
  {
    forn(j, K)
      a[i][i * K + j] = a[i + K][i + j * K] = 1;
    a[i][n] = a[i + K][n] = 1;
  }
  forn(i, K)
    forn(j, K)
      c[i * K + j] = -matrix[i][j];
  m--;

  forn(i, m)
  {
    int mj = -1;
    forn(j, n)
      if (!u[j] && fabs(a[i][j]) > eps)
        mj = j, j = n;
    if (mj == -1)
      memcpy(a[i], a[--m], sizeof(a[i])), i--;
    else
      u[p[i] = mj] = 1, Do(i, mj);
  }
  forn(i, K)
    x[i * K + i] = 1;

  forn(i, m)
  {
    dbl s = a[i][n];
    forn(j, n)
      s -= a[i][j] * x[j];
    assert(fabs(s) < eps);
  }

  int run = 1;
  forn(j, n)
    df[j] = c[j];
  forn(i, m)
    forn(j, n)
      df[j] -= a[i][j] * c[p[i]];
  fprintf(stderr, "Start Simplex!\n");
  while (run)
  {
    run = 0;
    forn(j, n) if (!u[j])
    {
      if (df[j] > eps && x[j] + eps < upper[j])
        run = 1, Change(j, 1, upper[j] - x[j]);
      else if (df[j] < -eps && x[j] - eps > lower[j])
        run = 1, Change(j, -1, x[j] - lower[j]);
    }
  }

  dbl res = 0;
  forn(i, n)
    res += x[i] * c[i];
  printf("%d\n", (int)(-res + 0.5));
  fprintf(stderr, "cnt1 = %d, N = %d, M = %d, K = %d\n", cnt1, n, m, K);
  return 0;
}