Description

A badminton team has $n$ male athletes and $n$ female athletes. You are given two $n \times n$ matrices $P$ and $Q$. $P_{i,j}$ is the male athlete $i$'s competitive advantage when paired with female athlete $j$ in mixed doubles; $Q_{i,j}$ is the female athlete $i$'s competitive advantage when cooperating with male athlete $j$.

However, due to various factors such as technical coordination and psychological state, $P_{i,j}$ is not necessarily equal to $Q_{j,i}$. The combined competitive advantage of the pair consisting of male athlete $i$ and female athlete $j$ is $\bm{P_{i,j} \times Q_{j,i}}$.

Now, design an algorithm to compute the optimal pairing between male and female athletes so that the sum of the combined competitive advantages across all pairs is maximized.

Input Format

The first line contains one positive integer $n$ $(1 \le n \le 20)$. The next $2n$ lines each contain $n$ numbers. The first $n$ lines are $P$, and the last $n$ lines are $Q$.

Output Format

Output the maximum possible sum of the combined competitive advantages across all pairs.

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

52

Hint

Translated by ChatGPT 5