程序设计能力实训

1050. 最小向量点积

单点时限: 2.0 sec

内存限制: 256 MB

两个向量 的点积定义为 :

例如,两个三维向量 的点积是

假设允许对每个向量中的坐标值进行重新排列。找出所有排列中点积最小的一种排列,输出最小的那个点积值。

上例中的一种排列 的点积为,这是最小的点积。

输入格式

行:一个整数 () 为问题数。

接下来每个问题有 行。第 行是一个整数 ,表示两个向量的维数。第 行和第 行分别表示向量 和向量 。每个向量都有 个由一个空格分隔的坐标值 组成。

输出格式

对于每个问题,输出一行问题的编号( 开始编号,格式:case #0: 等)。

然后对应每个问题在一行中输出最小点积值。

样例

Input
3
3
3 1 -5
-2 -1 4
1
2
-298
5
1 2 3 4 5
1 0 1 0 1
Output
case #0:
-27
case #1:
-596
case #2:
6
不限期开放

题目列表