题目描述

羽毛球队有男女运动员各 $n$ 人。给定 $2$ 个 $n \times n$ 矩阵 $P$ 和 $Q$。$P_{i,j}$ 是男运动员 $i$ 和女运动员 $j$ 配对组成混合双打的男运动员竞赛优势；$Q_{i,j}$ 是女运动员 $i$ 和男运动员 $j$ 配合的女运动员竞赛优势。

但是，由于技术配合和心理状态等各种因素影响，$P_{i,j}$ 不一定等于 $Q_{j,i}$。男运动员 $i$ 和女运动员 $j$ 配对组成混合双打的男女双方竞赛优势为 $\bm{P_{i,j} \times Q_{j,i}}$。

现在，请你设计一个算法，计算男女运动员最佳配对法，使各组男女双方竞赛优势的总和达到最大。

输入格式

第一行有 $1$ 个正整数 $n$ $(1 \le n \le 20)$。接下来的 $2n$ 行，每行 $n$ 个数。前 $n$ 行是 $P$，后 $n$ 行是 $Q$。

输出格式

将计算出的男女双方竞赛优势的总和的最大值输出。

3
10 2 3
2 3 4
3 4 5
2 2 2
3 5 3
4 5 1

52