CF575C Party

注意本题的内存限制不同寻常。 在 MDCS（Microsoft Development Center Serbia）工作的人们喜欢聚会。他们通常会在周五和周六去夜店。 有 $N$ 名员工在 MDCS 工作，城市里有 $N$ 家夜店。不幸的是，如果有超过一名微软员工在同一家夜店，酷炫程度会变得无限高，派对也就会结束，因此夜店老板绝不会允许同一周有超过一名微软员工进入他们的夜店（以防万一）。 你正在为微软员工组织夜生活活动，你手中有每个员工对所有夜店在周五和周六的喜欢程度的统计数据。 你需要将员工分配到夜店，以使他们的幸福总和最大化（他们的幸福感等同于他们对该夜店的喜欢程度）。同时，一半员工要在周五去夜店，另一半在周六去。

第一行包含整数 $N$，表示 MDCS 员工人数。 接下来有 $N \times N$ 的矩阵，矩阵第 $i$ 行第 $j$ 列的元素为整数，表示第 $i$ 个员工对于第 $j$ 家夜店的周五派对的喜欢程度。 然后是另一个 $N \times N$ 的矩阵，矩阵第 $i$ 行第 $j$ 列的元素为整数，表示第 $i$ 个员工对于第 $j$ 家夜店的周六派对的喜欢程度。 - $2 \leq N \leq 20$ - $N$ 为偶数 - $0 \leq$ 喜欢程度 $\leq 10^{6}$ - 所有值均为整数

输出一个整数，表示可能达到的最大幸福总和。

以下是我们如何分配员工与夜店的示例： 周五：第 $1$ 个员工与第 $4$ 家夜店（幸福值为 $4$），第 $4$ 个员工与第 $1$ 家夜店（幸福值为 $4$）。 周六：第 $2$ 个员工与第 $3$ 家夜店（幸福值为 $81$），第 $3$ 个员工与第 $2$ 家夜店（幸福值为 $78$）。 $4+4+81+78=167$。 由 ChatGPT 5 翻译