Party

Note the unusual memory limit for the problem.

People working in MDCS (Microsoft Development Center Serbia) like partying. They usually go to night clubs on Friday and Saturday.

There are N people working in MDCS and there are N clubs in the city. Unfortunately, if there is more than one Microsoft employee in night club, level of coolness goes infinitely high and party is over, so club owners will never let more than one Microsoft employee enter their club in the same week (just to be sure).

You are organizing night life for Microsoft employees and you have statistics about how much every employee likes Friday and Saturday parties for all clubs.

You need to match people with clubs maximizing overall sum of their happiness (they are happy as much as they like the club), while half of people should go clubbing on Friday and the other half on Saturday.

Input

The first line contains integer N — number of employees in MDCS.

Then an N × N matrix follows, where element in i-th row and j-th column is an integer number that represents how much i-th person likes j-th club’s Friday party.

Then another N × N matrix follows, where element in i-th row and j-th column is an integer number that represents how much i-th person likes j-th club’s Saturday party.

  • 2 ≤ N ≤ 20
  • N is even
  • 0 ≤  level of likeness  ≤ 106
  • All values are integers

Output

Output should contain a single integer — maximum sum of happiness possible.

Examples

input

4
1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3
5 8 7 1
6 9 81 3
55 78 1 6
1 1 1 1

output

167

Note

Here is how we matched people with clubs:

Friday: 1st person with 4th club (4 happiness) and 4th person with 1st club (4 happiness).

Saturday: 2nd person with 3rd club (81 happiness) and 3rd person with 2nd club (78 happiness).

4+4+81+78 = 167

Solution:

#include <bits/stdc++.h>

using namespace std;

template<typename T>
class hungarian {
public:
const int n;
const int m;
T a[21][21];
T u[21];
T v[21];
int pa[21];
int pb[21];
int way[21];
T minv[21];
bool used[21];
T inf;

hungarian(int _n, int _m) : n(_n), m(_m) {
assert(n <= m);
    fill(u, u + n + 1, 0);
    fill(v, v + m + 1, 0);
    fill(pa, pa + n + 1, -1);
    fill(pb, pb + m + 1, -1);
    inf = numeric_limits<T>::max();
}

inline void add_row(int i) {
fill(minv, minv + m + 1, inf);
fill(used, used + m + 1, false);
pb[m] = i;
pa[i] = m;
int j0 = m;
do {
used[j0] = true;
int i0 = pb[j0];
T delta = inf;
int j1 = -1;
for (int j = 0; j < m; j++) {
        if (!used[j]) {
          T cur = a[i0][j] - u[i0] - v[j];
          if (cur < minv[j]) {
            minv[j] = cur;
            way[j] = j0;
          }
          if (minv[j] < delta) {
            delta = minv[j];
            j1 = j;
          }
        }
      }
      for (int j = 0; j <= m; j++) {
        if (used[j]) {
          u[pb[j]] += delta;
          v[j] -= delta;
        } else {
          minv[j] -= delta;
        }
      }
      j0 = j1;
    } while (pb[j0] != -1);
    do {
      int j1 = way[j0];
      pb[j0] = pb[j1];
      pa[pb[j0]] = j0;
      j0 = j1;
    } while (j0 != m);
  }

  inline T current_score() {
    return -v[m];
  }

  inline T solve() {
    for (int i = 0; i < n; i++) {
      add_row(i);
    }
    return current_score();
  }
};

int friday[42][42];
int saturday[42][42];
int ans;
int n;
int old_u[21][21], old_v[21][21], old_p[21][21];

void dfs(hungarian<int> &h, int i, int fridays, int saturdays) {
if (i == n) {
ans = max(ans, -h.current_score());
return;
}
for (int rot = 0; rot < 2; rot++) {
    if (rot == 0 && fridays == n / 2) {
      continue;
    }
    if (rot == 1 && saturdays == n / 2) {
      continue;
    }
    for (int j = 0; j < n; j++) {
      h.a[i][j] = -(rot == 0 ? friday[i][j] : saturday[i][j]);
    }
    for (int j = 0; j <= n; j++) {
      old_u[i][j] = h.u[j];
      old_v[i][j] = h.v[j];
      old_p[i][j] = h.pb[j];
    }
    h.add_row(i);
    dfs(h, i + 1, fridays + (rot == 0), saturdays + (rot == 1));
    for (int j = 0; j <= n; j++) {
      h.u[j] = old_u[i][j];
      h.v[j] = old_v[i][j];
      h.pb[j] = old_p[i][j];
    }
  }
}

int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      scanf("%d", friday[i] + j);
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      scanf("%d", saturday[i] + j);
    }
  }
  hungarian<int> h(n, n);
ans = 0;
dfs(h, 0, 0, 0);
printf("%d\n", ans);
return 0;
}