← 返回题目列表

Codeforces · 575/C

C. 聚会

中文机器翻译题面 查看原题

请注意该问题的异常内存限制。

在 MDCS(塞尔维亚微软开发中心)工作的人喜欢参加派对。他们通常在周五和周六去夜总会。

MDCS 有 N 人工作,该市有 N 个俱乐部。不幸的是,如果夜总会里有不止一名微软员工,那么酷感就会无限高,派对就会结束,所以俱乐部老板永远不会让超过一名微软员工在同一周内进入他们的俱乐部(只是为了确定)。

您正在为 Microsoft 员工组织夜生活,并且您有关于每个员工对所有俱乐部周五和周六聚会的喜爱程度的统计数据。

你需要将人们与俱乐部相匹配,以最大化他们的总体幸福感(他们对俱乐部的喜爱程度与他们的幸福程度一样),而一半的人应该在周五去俱乐部,另一半人应该在周六去俱乐部。

输入

第一行包含整数 N — MDCS 中的员工数量。

然后是一个 N × N 矩阵,其中第 i 行第 j 列的元素是一个整数,表示第 i 个人对第 j 个俱乐部的周五聚会的喜欢程度。

接下来是另一个 N × N 矩阵,其中第 i 行第 j 列的元素是一个整数,表示第 i 个人对第 j 个俱乐部的周六聚会的喜欢程度。

- 2 ≤ N ≤ 20
- N 是偶数
- 0 ≤ 相似度 ≤ 106
- 所有值均为整数

输出

输出应包含一个整数 - 可能的幸福感的最大总和。

示例

输入 #1

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

输出 #1

167

注意

以下是我们将人员与俱乐部进行匹配的方式:

星期五:第 1 个人拥有第 4 俱乐部(4 幸福),第 4 个人拥有第 1 俱乐部(4 幸福)。

星期六:第 2 个人拥有第 3 俱乐部(81 幸福),第 3 个人拥有第 2 俱乐部(78 幸福)。

4+4+81+78 = 167