Description

给定两个向量 $v_1 = (x_1, x_2, ..., x_n)$ 和 $v_2 = (y_1, y_2, ..., y_n)$。这两个向量的标量积是一个单一的数，计算方式为 $x_1y_1 + x_2y_2 + ... + x_ny_n$。

现在你可以任意排列每个向量的坐标。请选择两个排列，使得这两个新向量的标量积尽可能小，并输出这个最小的标量积。

Input Format

输入文件的第一行包含一个整数 $T$，表示测试用例的数量。对于每个测试用例，第一行包含一个整数 $n$。接下来的两行每行包含 $n$ 个整数，分别表示 $v_1$ 和 $v_2$ 的各个坐标。

Output Format

对于每个测试用例，输出一行：

Case #$X$: $Y$

其中 $X$ 是测试用例编号（从 1 开始），$Y$ 是所有排列下两个向量的最小标量积。

2
3
1 3 -5
-2 4 1
5
1 2 3 4 5
1 0 1 0 1

Case #1: -25
Case #2: 6

Hint

数据范围

小数据集（5 分，测试集 1 - 可见）

• $T = 1000$
• $1 \leq n \leq 8$
• $-1000 \leq x_i, y_i \leq 1000$

大数据集（10 分，测试集 2 - 隐藏）

• $T = 10$
• $100 \leq n \leq 800$
• $-100000 \leq x_i, y_i \leq 100000$

由 ChatGPT 4.1 翻译