Minimum Scalar Product (Large)

You are given two integer vectors of the same length, $v_1 = (x_1, x_2, \dots, x_n)$ and $v_2 = (y_1, y_2, \dots, y_n)$. The scalar product of the two vectors is the single number $x_1 y_1 + x_2 y_2 + \dots + x_n y_n$.

You may reorder the coordinates of each vector however you like. Permute the coordinates of both vectors so that the scalar product is as small as possible, and print that minimum.

The first line contains the number of test cases $T$.

Each test case takes three lines. The first line contains an integer $n$. The next two lines contain $n$ integers each: the coordinates of $v_1$ on the second line and the coordinates of $v_2$ on the third line.

Limits

• $1 \le T \le 10$
• $1 \le n \le 800$
• $-100000 \le x_i, y_i \le 100000$

For each test case, print one line in this format.

Case #X: Y

$X$ is the test case number starting from 1, and $Y$ is the smallest scalar product obtainable by permuting the coordinates of the two vectors.