题目描述

LCR 当上了少女乐队社的指导老师，她要找一群女孩子组乐队。一支乐队必须由五个人组成。已经有部分少女主动报名，现在乐队还差 $k(2 \le k \le 5)$ 个人。

学校里总共还有 $N$ 名少女可以组乐队，第 $i$ 个人擅长的乐器是 $a_i$，相性是 $b_i$。

LCR 需要招募 $k$ 名少女，她们擅长的乐器必须互不相同。

队内气氛的活跃度是被选出 $k$ 个少女两两相性差绝对值的最小值：

原有主动报名的成员不影响活跃度，只有这 $k$ 个人影响。

LCR 想组一个队内气氛最活跃的队伍，请你帮他计算出这个最大可能的活跃度。题目保证一定有解。

输入格式

第一行输入 $T$，表示一共 $T$ 组测试数据。

对于每组测试数据： 第一行三个正整数 $N,k,TP$，表示可选的人数，需求的人数，测试数据类型。$TP$ 用于识别测试点类别。 接下来 $N$ 行，每行两个正整数 $a_i,b_i$，表示第 $i$ 名少女擅长的乐器以及相性值。

输出格式

输出一个数字，表示最大可能的队内气氛活跃度。

样例输入 #1

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

样例输出 #1

2

样例解释：选择第1、3、5名少女，乐器分别为 $1,3,2$ 互不相同。 $\min(|1-3|,|3-5|,|1-5|)=2$。

数据范围

• 测试点1：$N \le 100,\ TP=1$
• 测试点2：$N \le 1000,\ k=5,\ 1\le a_i \le5,\ TP=2$
• 测试点3：$N \le 1000,\ k=5,\ TP=3$
• 测试点4：$N \le 10000,\ k=3,\ TP=4$
• 测试点5：$N \le 10000,\ k=5,\ 1\le a_i \le5,\ TP=5$
• 测试点6：$TP=6$

对于所有数据： $\red{1 \le N \le 10000,\ 2 \le k \le5,\ 1 }$$\red{\le a_i \le N,\ 1 \le b_i \le 10^6,\ T \le5}$。