问题描述

平面直角坐标系上有 $n$ 个点，其中第 $i$ 个节点的坐标为 $(x_i,y_i)$。

现以如下方式生成一张无向图 $G$，其中图中共有 $n$ 个节点 $\frac{n(n+1)}{2}$ 条边，第 $i$ 个点和第 $j$ 个点之间的边的边权为 $|x_i-x_j|+|y_i-y_j|$，即两点之间的曼哈顿距离。

一个环的大小定义为经过所有边的边权之和，小 $M$ 想知道图中最大的 $k$ 元环的大小，请你输出这个 $k$ 元环的大小。

一条经过 $k+1$ 个点的路径 $(i_1,i_2,…,i_{k+1})$ 被称为 $k$ 元环，当且仅当 $i_1,i_{k+1}$ 相同且 $i_1,i_2,i_3,…,i_k$​ 两两不同。

输入格式

本题共有 $T$ 组数据。

输入第一行，包含一个正整数 $T$，之后对于每组数据：

第一行包含 $2$ 个正整数 $n,k$。

第二行包含 $n$ 个整数，表示 $x_i$​。

第三行包含 $n$ 个整数，表示 $y_i$。

输出格式

对于每组数据，输出 $1$ 行，输出 $1$ 个整数，表示最终答案。

样例输入

5
5 3
1 2 3 4 5
10 9 8 7 6
6 5
1 1 4 5 1 4
1 9 1 9 8 10
3 3
1 2 3
4 5 6
4 4
1 2 3 4
9 8 9 8
3 3
1 1 1
2 2 2

样例输出

16
48
8
10
0

样例解释

对于第一组数据，一种合法的最大的环为 $(1,10),(5,6),(2,9)$。

对于第二组数据，一种合法的最大的环为 $(1,9),(4,1),(4,10),(1,1),(5,9)$。

对于第三组数据，一种合法的最大的环为 $(1,4),(2,5),(3,6)$。

对于第四组数据，一种合法的最大的环为 $(1,9),(2,8),(3,9),(4,8)$。

对于第五组数据，一种合法的最大的环为 $(1,2),(1,2),(1,2)$。

评测数据规模

对于 $20\%$ 的数据，$k=3$。

对于另外 $20\%$ 的数据，$x_i=y_i$。

对于所有测评数据，$3 \leq k \leq n \leq 1000,0 \leq x_i,y_i \leq 10^7,k \leq 6$。

数据保证每组数据的 $n$ 之和不超过 $1000$​。