CF575C.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.

注意本题的内存限制较为特殊。

在微软塞尔维亚开发中心（MDCS，Microsoft Development Center Serbia）工作的人们热衷于聚会，通常会在周五和周六去夜店。

MDCS 共有 $N$ 名员工，而该城市中恰好也有 $N$ 家夜店。不幸的是，若同一家夜店内出现两名及以上微软员工，则现场“酷炫值”将无限飙升，导致派对立即终止；因此，为确保万无一失，所有夜店老板均严格规定：同一周内，每家夜店最多只允许一名微软员工入内。

你负责为微软员工组织周末夜生活，并已掌握一份统计数据：其中记录了每名员工对每家夜店在周五与周六两晚的喜爱程度。

你的任务是将员工与夜店进行匹配，使得所有员工的总幸福度（即每人对其所分配夜店的喜爱程度之和）最大化；同时需满足约束：恰好一半员工在周五去夜店，另一半则在周六去夜店。

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

第一行包含一个整数 $N$ —— MDCS 公司的员工人数。

随后是一个 $N \times N$ 的矩阵，其中第 $i$ 行第 $j$ 列的元素是一个整数，表示第 $i$ 位员工对第 $j$ 个俱乐部的周五派对的喜爱程度。

接着是另一个 $N \times N$ 的矩阵，其中第 $i$ 行第 $j$ 列的元素是一个整数，表示第 $i$ 位员工对第 $j$ 个俱乐部的周六派对的喜爱程度。

• $2 \leq N \leq 20$
• $N$ 为偶数
• 喜爱程度满足 $0 \leq \text{level of likeness} \leq 10^6$
• 所有数值均为整数

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

输出应为一个整数——可能的最大幸福值总和。

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

我们是这样将人员与俱乐部匹配的：

周五：第1个人与第4个俱乐部（幸福值为4），第4个人与第1个俱乐部（幸福值为4）。

周六：第2个人与第3个俱乐部（幸福值为81），第3个人与第2个俱乐部（幸福值为78）。

4 + 4 + 81 + 78 = 167