题目描述

羽毛球队有男女运动员各 nnn 人。给定 222 个 n×nn \times nn×n 矩阵 PPP 和 QQQ。Pi,jP_{i,j}Pi,j​ 是男运动员 iii 和女运动员 jjj 配对组成混合双打的男运动员竞赛优势；Qi,jQ_{i,j}Qi,j​ 是女运动员 iii 和男运动员 jjj 配合的女运动员竞赛优势。

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

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

输入格式

第一行有 111 个正整数 nnn (1≤n≤20)(1 \le n \le 20)(1≤n≤20)。接下来的 2n2n2n 行，每行 nnn 个数。前 nnn 行是 PPP，后 nnn 行是 QQQ。

输出格式

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

3

10 2 3

2 3 4

3 4 5

2 2 2

3 5 3

4 5 1

52

提示

保证题目数据均在 int\text{int}int 类型范围内。