题目描述

羽毛球队有男女运动员各$\red{n}$人。给定$\red{2}$ 个$\red{n×n}$矩阵$\red{P}$和$\red{Q}$。$\red{P[i][j]}$是男运动员$\red{i}$和女运动员$\red{j}$配对组成混合双打的男运动员竞赛优势；$\red{Q[i][j]}$是女运动员$\red{i}$和男运动员$\red{j}$配合的女运动员竞赛优势。由于技术配合和心理状态等各种因素影响$\red{，P[i][j]}$不一定等于$\red{Q[j][i]}$。男运动员$\red{i}$和女运动员$\red{j}$配对组成混合双打的男女双方竞赛优势为$\red{P[i][j]×Q[j][i]}$。设计一个算法，计算男女运动员最佳配对法，使各组男女双方竞赛优势的总和达到最大。 编程任务：设计一个算法，对于给定的男女运动员竞赛优势，计算男女运动员最佳配对法，使各组男女双方竞赛优势的总和达到最大。

输入格式

第一行有$\red{1}$ 个正整数$\red{n (1≤n≤20)}$。接下来的$\red{2n}$行，每行$\red{n}$个数。前$\red{n}$行是$\red{p}$，后$\red{n}$行是$\red{q}$。

输出格式

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

样例

输入样例

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

输出样例

52