#18. Genius ACM

Genius ACM

给定一个整数 MM,对于任意一个整数集合 SS,定义“校验值”如下:

从集合 SS 中取出 MM 对数(即 2M2∗M 个数,不能重复使用集合中的数,如果 SS 中的整数不够 MM 对,则取到不能取为止),使得“每对数的差的平方”之和最大,这个最大值就称为集合 SS 的“校验值”。

现在给定一个长度为 NN 的数列 AA 以及一个整数 TT

我们要把 AA 分成若干段,使得每一段的“校验值”都不超过 TT

求最少需要分成几段。

输入格式

第一行输入整数 KK,代表有 KK 组测试数据。

对于每组测试数据,第一行包含三个整数 N,M,TN,M,T

第二行包含 NN 个整数,表示数列A_1,A_2A_NA\_1,A\_2…A\_N

输出格式

对于每组测试数据,输出其答案,每个答案占一行。

数据范围

1K121 \le K \le 12, 1N,M5000001 \le N,M \le 500000, 0T10180 \le T \le 10^{18}, 0A_i2200 \le A\_i \le 2^{20}

输入样例:

2
5 1 49
8 2 1 7 9
5 1 64
8 2 1 7 9

输出样例:

2
1