Description

Xiao T (小 T) plans to place several paintings at home. He has bought $N$ paintings and $N$ frames. To show his taste, he wants to match paintings with frames so that the result is neither too plain nor too jarring.

For the pairing of painting $i$ with frame $j$, Xiao T assigns a plainness value $A_{i, j}$ and an incompatibility value $B_{i, j}$. The overall disharmony of a complete matching is defined as the product of the sum of plainness values over all matched pairs and the sum of incompatibility values over all matched pairs. Specifically, let painting $i$ be matched with frame $p_i$; then the overall disharmony is

$$\mathrm{disharmony}=\sum_{i=1}^{N}A_{i,p_i}\times \sum_{i=1}^{N}B_{i,p_i}.$$

Xiao T wants to know the minimum possible overall disharmony.

Input Format

The first line contains a positive integer $T$, the number of test cases. For each test case:

• The first line contains a positive integer $N$, the number of paintings and frames.
• Lines $2$ through $N+1$ each contain $N$ non-negative integers; on line $i+1$, the $j$-th number is $A_{i, j}$.
• Lines $N+2$ through $2N+1$ each contain $N$ non-negative integers; on line $i+N+1$, the $j$-th number is $B_{i, j}$.

Output Format

Output $T$ lines, each containing one integer: the minimum overall disharmony.

1
3
4 3 2
2 3 4
3 2 1
2 3 2
2 2 4
1 1 3

30

Hint

If painting $1$ is matched with frame $3$, painting $2$ with frame $1$, and painting $3$ with frame $2$, then the overall disharmony is $30$.

Constraints: For $100\%$ of the testdata, $N \leq 70$, $T \leq 3$, $A_{i, j} \leq 200$, $B_{i, j} \leq 200$.

Translated by ChatGPT 5