3754: 佛怒火莲(第五轮04)
题目描述
某中二少年 AQx 看完《斗破苍穹》以后就在YY自己能不能搓得出佛怒火莲（一 个技能）。
这个技能需要融合五种不同属性的火焰。
现在，火焰商店里面摆着一排N堆火焰，第i堆火焰的属性（类似风雷电）是ai， 不稳定度是bi 。
已知，佛怒火莲需要凑齐恰好k种属性不同的火焰才能释放，释放时的威力计算 方式如下：
假设选择的k种火焰的不稳定度排序后分别是b1, b2, b3, . . . , bk，那么，这一发佛怒 火莲的威力是min
i − bi+1 |， 也就是按bi 排序后， 相邻两个火焰不稳定度的 差的最小值。
现在， FFY 想搓一个威力最大的火莲，请帮助 FFY 计算， 他能搓出的火莲， 威力最大是多少？
输入
第一行输入T，表示一共T组测试数据。 对于每组测试数据：
第一行三个正整数N, k, TP，表示火焰个数，需求的属性种类数，以及测试数据类 型， TP有助于你识别这是哪一类测试数据。
接下来N行，每行两个正整数ai， bi，表示第i个火焰的属性和不稳定度。
输出
一个数字表示答案，数据保证一定有解。
样例输入 复制
1
5 3 1
1 1
1 2
3 3
2 4
2 5样例输出 复制
2提示
样例 1 说明】
选择{1,3,5}这三个火焰，凑齐了三种不同的a，威力是min(∣ 1 − 3 ∣, ∣ 3 − 5 ∣) = 2。
【数据范围】
测试点1 − 2： N ≤ 100, TP = 1。
测试点3 − 6： N ≤ 1000, k = 5,1 ≤ ai ≤ 5, TP = 2。
测试点7 − 10： N ≤ 1000, k = 5, TP = 3。
测试点11 − 14： N ≤ 10000, k = 3, TP = 4。
测试点15 − 17： N ≤ 10000， k = 5,1 ≤ ai ≤ 5, TP = 5。 测试点18 − 20： TP = 6。
对于所有数据： 1 ≤ N ≤ 10000,2 ≤ k ≤ 5,1 ≤ ai ≤ N, 1 ≤ bi ≤ 10^6 ， T ≤ 5。